I feel you. I had my email on OVH for a while, but they handle abuse so bad that Apple just blanketed banned the /17 my IP was in. And I was lucky that Apple actually answered my emails and explained why I was banned. I doubt Microsoft and Google would give you any useful information.