Thanks for suggestion but I'm not sure how would Memcache fit in since:

If you have a high-traffic site that is dynamically generated with a high database load that contains mostly read threads then memcached can help lighten the load on your database.

Though there is one part of the system where caching could help - in cases where we recently did some of those remote stuff (DNS/HTTP) so we wouldn't need to to it again if it's in cache.

The thing here is that there are a lot of updates - and it is very important to maintain in what "state" the processing of a record is. Everything is payed per record by both our clients to us and us to business associates :)