The problem is that your VM provider is (unwittingly) offering the same address space to spammers. Maybe the spammer was using random addresses in the range? Or someone was starting up misconfigured smtp servers permitting relaying.

Running an outbound smtp server on a customer ip-range is going to be problematic anyway. All such ranges can be considered suspicious since the spammers who use them don't care about their standing.