Office 365 email user receiving NDRs when sending outside of our organization

We have a single user who is unable to send email outside of our organization due to multiple kickbacks with following NDR
Remote Server returned '550 5.7.501 Service unavailable. Banned Sender
I have verified by searching the various online spam lists ( spamhaus, etc) that our domain is not on any list and the issue does not seem to be effecting any of our other users. This user had his account hacked last week and we discovered it was used to send a large amount of spam before we reset his account.
I am unable to find a solution to resolve kickbacks for a single email address.
Jason ShawAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Vasil Michev (MVP)Commented:
Open a support case, he's probably listed on the internal blacklist. You can also try the self-service delisting functionality: go to the Office 365 portal -> Exchange -> Protection -> Action center and if the user is listed there, remove him.
Jason ShawAuthor Commented:
Thanks. I removed him in the action center after I read your post. Is that an instant resolution or does that take time to process? I ran a test after removing him in the action center and still kicked back. According to kickback, indication is recipient email provider is rejecting it
timgreen7077Exchange EngineerCommented:
Does the rejection come from all external recipients or just select ones?
Maximize Customer Retention with Superior Service

The IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy for valuable how-to assets including sample agreements, checklists, flowcharts, and more to help build customer satisfaction and retention.

Jason ShawAuthor Commented:
I tried gmail, yahoo and another provider and all rejected. Not being rejected internally though
timgreen7077Exchange EngineerCommented:
Oh ok, then yes it seems that O365 may be blocking the sender. @Vasil Michev (MVP) solution may be correct, and if you removed the sender from the internal blacklist there may be a replication period. I would give it at least an hour. If issue still happens after that, reach out to O365 free support.
Jason ShawAuthor Commented:
I will try a little patience and test again! lol Thanks!
timgreen7077Exchange EngineerCommented:
Sure thing and good luck.
Vidit BhardwajAdminCommented:
Try changing the primary SMTP address to something else and keep the current one as secondary so the new email address will be published outside and it might allow you to send the emails
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.