This sadly is very common. It is getting more common by the day it seems but this practice has started almost a decade ago.
An easy work around is to use a custom port as they seem to just block port 25 as a bad port but leave just about everything else open including 2525 which seems to be a common secondary smtp port for hosting companies.
