I had this problem in the beginning (specifically and only with hotmail), but it solved itself at some point. No idea if it was something that fastmail did or that hotmail did.

I have been using fastmail for one year and had zero other problems. If we don't move away from gmail, we will lose email, which is one of the only true decentralized and free protocols still left.