well, the type of company I'm looking for does the registrations for you, eg, they'll handle all the various country names you want, eg, .co.za for the generalized South Africa cctld.
Some countries require a physical presence to assign a domain. South Africa has .za, which requires a physical presence. In that case, they act as a trustee - they have registered agents in many countries.
The ones you listed are "normal" registrars that mostly handle the standard TLDs, plus, generally, .co.uk, .asia, and alternative TLDs like .me, .biz, etc..
A promising company is
http://www.marcaria.com/register/default.asp - I'm waiting for a callback now..