My experience suggests that you should progress step by step (I'm second to GVA Dispatch on that) - if your have plenty of time for a particular flight, try to deal yourself. You will find that in many countries the addresses and phones listed in jepps/cap555/aip/etc are not really the contacts for individuals who are dealing with permits, it is often general numbers and switch boards. After some time you will have your own address book for "right" people. In many (if not most) cases it is essensial to talk to permit department, not just sending them a fax/sita/aftn message. Actually it is a small world, even in big countries it is usually just 2-3 people who dealing with permits and after some time you will start to recognise their voice over a phone

After establishing an "individual" contacts you will also get some out-of-hours phone numbers which are not published anywhere but you need them to do something in the evening/night/weekend time.
To be successfull with some of the countries you also expected to talk with them in their language (for ex-colonies and French/Spanish/Portugese/etc countries). And still there are some countries where you need to use agents, just accept it as a fact.
Send fax/aftn/sita as approapriate and unless it is a country known for a hassle-free and swift replies, give them a call in 15-30 minutes to verify they've got your application and aware of it. Very often your applications could be "lost".
On application we usually using this format:
Herewith [airline name] kindly requests landing/overflight permission for the following flight:
operator:
callsign:
aircraft type: [specify acft type both in code and plain language]
aircraft reg:
mtow:
route: [put both ICAO and IATA codes for org/dst airports]
schedule: [in UTC]
purpose of the flight: [describe in short what you carry and sometimes for what reason, or ferry/empty]
for some countries you should also put number of crew and their nationalities, some countries also want to see airspace entry/en-route/exit points with timing.
Otherwise for urgent matters and for CIS/Middle East/African countries (unless you already familiar with getting permits there) go to the agents.
Hope it helps.