> 2. Some bad guy from the same IP network sent spam (although GMail error message specifically states that spam was sent by this exact IP address, not an address from the same network).

This is the most likely situation. If a VPS provider is sufficiently cheap, it will attract the wrong people, who will then get the entire VPS provider's IP blocks blacklisted.

It's a shame, but it's the reality. There are lots of discussions around this subject on various mailing lists, where people from the likes of Gmail have chimed in stating as much.

I would reckon it takes as little as 10% of the addresses in a /24 (so ~25 IPs) to get that entire netblock blacklisted.

If you want a higher probability of clean IPs, you need to be using a provider that is sufficiently expensive to not attract spammers.

Either that, or you need your own IPs.