I contacted Microsoft, actually received an answer from them and got an IP unblocked. Google can be tough though. If their Algorithms don't like you, good look

I contacted Microsoft, actually received an answer from them and got an IP unblocked. Google can be tough though. If their Algorithms don't like you, good look. I was responsible for a new IP/Email setup and while all other relevant providers liked our mail and Google Postmaster tools didn't show anything bad, all our mail went to Spam in GMail. I found out why when even mails from completely different senders would usually go to Inbox but hit Spam once our Website or email was included: Despite showing it as "high reputation", GMail must have considered it as utter trash. Changed to a different, older domain and all has been fine since.