Unfortunately there isn't much more you can do other than wait.
If you have been listed on 4 different blacklists, your issues won't be just with Microsoft servers, though those are the only ones you're concerned about at this time.
Sendgrid will need to go through the motions to have you removed from the blacklists.
I have encountered issues before where even after a client was removed from the blacklists they where still blocked from Microsoft servers for a while. In speaking with Microsoft support, I was told the client would remain blocked until they didn't appear on the blacklists for a defined period of time. As I recall, it was 3 months, but your situation could be different.