abandon your server and re-create a new VPS until you get a clean IP, since you just started.
With regards to Gmail and Microsoft being sent to spam…