"Wouldn't surprise me if Linode were entirely blocked."

I'd be very surprised. I hosted email on Linode for years without issue.