Is this paid for hosting or a server hosted at home? Check firewall, use it to block outgoing ports as well as incoming. You can also use tools like ntop to check network traffic into and out of the box. If you're not sure, wipe it and reinstall and secure it again.
If you're confident it's not been hacked, ask for a different IP outside of the affected block.