I was in the middle of a migration from Exchange 2003 to 2010 and was troubleshooting public folder replication when I noticed my replication emails to the new public folder database were stuck in the unreachable messages queue.
The solution is to simply restart the SMTP service:
net stop smtpsvc
net start smtpsvc
Then the messages flowed out the appropriate connector.
