It appears that Nokia Messaging is working again. I did send an email to Nokia USA customer care. They only responded with "sorry for the inconvenience" and also asked for my IMEI number.

Regardless, I am now receiving push messages and can also log into my account at email.nokia.com again.

I don't know if my email to customer care prompted them to do something or not. Or maybe there was just a system outage.