I was actually hosting on Linode (UK). My hunch was that they would be one of the more reputable networks; I've run small mail servers on them before (2+ years ago) without any problems.

It's a pity there's no easy way (that I know of) to look up the reputation for an entire network block. I'm glad to hear your experience with Linode matches mine.