Mails are going out. It's just that for whatever !@#$ed-up reason gmail and hotmail have changed their spam policies so they let more real spam through and filter out more non-spammers. Their website where they tell you their rules are completely opaque, I know international standard documents that are easier to understand.
I've been planning to move my mail server for a long time, which may or may not fix this issue.