fastmail.fm is where people disillusioned with GMail traditionally go.

Have you heard any story similar to what's happening with OP where fastmail support ended up resolving the issue quickly and in a timely manner?

I'm not trying to imply that it would be the same, genuinely curious if I can expect better by switching.

Not that I'm aware of. I think there's an element of "grass is always greener on the other side." When the NSA thing first came out, people were publicly talking about leaving for GMail for Fastmail, since Google showed up in the XKeyscore docs, just as people felt superior about their Androids when the Apple Foxconn scandal broken. But in all likelihood they suffer from many of the same problems; Fastmail (and the various Android manufacturers) are just smaller and don't attract the same negative attention.

I haven't had my account hijacked before with fastmail. But I have had to contact support and I was in touch with a real person in less than 30 minutes.

I have dealt with Fastmail support in the past, although it was regarding invoicing questions, not identity fraud. My experiences were fairly positive.

can't say enough good things about fastmail