Your best option, as what ximi said to do.
Create a backup of everything and then get the datacenter to format and reinstall (or do it over KVM if the DC has it). When its re-installed I would then consider paying a company to secure down the system for you, if this is for business use then I would definately recommened getting a consultant to run things by (such as leaving MySQL open, although needed you need to lock it down).
Consider getting them to install an intrusion detection system and monitor failed logins on everything, it could have been that he is brute forcing (you've said you have strong passwords, but you never know).
Also ensure that there is nothing on the PC you are connecting from, as if you have a keylogger on your system then you are always going to have the same problem