Answering your question, iOS 4 allows apps to run in the background, but that doesn't work the same way as on the desktops. Background running apps should use very low memory and will be purged as soon as enough apps need the memory in front of it. So what you really need is pushing chat notifications, which helps save your phone battery because it's less power intensive and handled by the system.
Nimbuz is another great free option that also supports voice calling, many IMs, push (from experience I think it lasts between 24 hours and 3 days top), and used to work even with skype voice. now there's no third party client that works with skype at all as far as I know.
It is my current favorite and I've tried many options, tho I haven't tried Trillian nor Beejive.
Fring is the first one for iPhone and is still great as well. It features video calling (between 2 frings). I prefer Nimbuzz because of little details, such as fring doesn't show from which protocol the specific profile is in the list.
In the end, the app you choose will be the best one for your personal taste, as there are plenty of good options.