I've just deployed a new hosting server (hosting-5.) It's running on the new network setup, running CentOS 5.3 32-bit, and generally seems quite well-behaved.
I'm going to migrate everyone on the old Fedora Core 6 hosting server over to this over the next week and then finally retire it.
EDIT: I've migrated a couple of customer VMs onto it (with their permission, of course!) and it has fixed their stability. Even Ubuntu VMs, traditionally having been very unstable, are now stable once again. Success!