If it's been without updates for more than a month or so, I treat any Internet-touching system as hacked. It's just not worth assuming there isn't a trojan or something equally horrible running on there. In your case you have systems that are years of serious security issues behind the curve.
So, no good news from me. You've got a bit of work to do I'm afraid.
Work out what these machines did and backup unique data.
If there is working data (eg websites, databases, etc) get ready to pick those apart with a fine comb. Abandoned Wordpress, Drupal, PHPBB, etc sites are wonderful things for hacking. You get all sorts of mucky shells laid in there and often —once hacked— admin credentials are injected into the databases.
If these are just desktops or internal-only (by firewall) servers you have less to do.
Nuke from orbit and reinstall a current LTS.
Ubuntu 14.04 or wait a month or two and go 16.04. These have five years support from release so set a reminder.
Don't upgrade. I'm serious. Not only is upgrading from 9.04 hard (you have to fake repo locations and upgrade multiple times, but so much has changed between these ancient versions and what we use today. It's simply easier to install afresh.
Redeploy the services.
Essentially restoring everything that was running in step one. Chances are you can do a better job of laying it out too. Perhaps integrate some CI or testing to automate the maintenance tasks your predecessor hated to do.
Think of this as an opportunity ☺ There's other stuff you can cram into this cycle too. Hardware upgrades. Consolidation. All the sort of stuff you wouldn't want to try out on a live server.
It is always tempting to cut corners, especially when you have a job like this foisted on you. I've been there. Your predecessor was neglectful and you have an uphill battle ahead of you. Given your experience I wouldn't even bemoan you wanting to switch to a Red Hat derivative at this point. If it really makes your life easier, make it so.
Just make sure that you do a better job for the next guy.