I had a working environment with exchange 2003on a 2003 server and exchange 2010 on a 2008 R2 server and a bidirectional routing group in between.
I was in the process of migrating mailboxes from 2003 to 2010, when suddenly one of the mailbox migrations failed with an error message implying insufficient rights. I was investigating as people started complaining about missing inbound mail, and outbound mail stuck in the out-box.
I then found that the CA-service on my certificate server had stopped, and would not start again. (Bad key) Following advice from microsoft forums, I reinstalled CA, and restored the latest backup . Now both exchange 2003 and 2010 starts without errors, but the routing group connector on the 2003 is stuck with 110 messages. The CA is used for the 2003 only.