> when the IP range it's on becomes greylisted in UCE-PROTECT -- which happens every so often
This is a common complaint with Linode specifically, but probably fairly common with low-cost virtual server providers in general. It's worth looking into the history of your IP before you start using it to host mail, and if it's feasible, shelling out for a dedicated server (ideally from a provider that doesn't also offer virtual servers, or has enough network separation between them) makes it much less likely that your neighbour is a spammer. Mine's never been on UCE-PROTECT.
The only nag is that Microsoft is EXTREMELY strict for their hosted email. It's the only provider that consistently denies recieving mail from my server when the IP range it's on becomes greylisted in UCE-PROTECT -- which happens every so often...
Easily solved with getting the MX and backup MX IP's whitelisted there, but I haven't bothered cashing out for that yet...