Phil,
Greetings from across the pond.
Is there any chance that Microsoft since upgrading to their new Windows Live servers/clouds have changed their black/white listing policy?
They may have even had a "reset" on their white lists which is causing the problem.
A couple of other things to check, though. If you have an email address that is physically on your web server, try sending an email from it to your hotmail account to make sure your server isn't just being outright rejected.
The next thing to check would be to make sure that your UE instance is sending all the necessary headers (to, from, reply-to, etc.). While some email servers won't mind if something is missing, my guess is that hotmail/MSFT wants everything to be perfect.
Good luck,
Brian