I've used a paid email provider since before Gmail existed. They've not been blocked.
I know there are the occasional posts on HN about Gmail blocking their servers, but I doubt it's anywhere close to the norm.