Removing Routing Groups...

You didn't decommission your old server properly. I assume that Active Directory still knows about it.

The error happens when you manually create a Routing Group Connector in Exchange 2007 with the parameter "-Bidirectional $true" which is what Technet gives an an example. The Installation of Exchange 2007 creates individual routing connectors for each direction with different names.

You can use Get-RoutingConnector |fl to show the full details of the routing connectors, but that's not going to help you in your quest to remove them. For that you need to use adsiedit.msc from Windows Support Tools. If they're not installed, then install them from the Windows 2003 CD.

You can delete the connectors in adsiedit, but I'd suggest that you simply rename them and then go back to Exchange Management Shell (because when you make changes with adsiedit, you are directly modifying Active Directory - delete the wrong thing here and you'll have a world of pain).

The containers that your connectors are in are as follows:
(Start adsiedit.msc and expand Configuration. Then expand as appropriate)

CN=Configuration,
CN=Services,
CN=Microsoft Exchange,
CN=<Your Exchange Org>,
CN=<Exchange 2000/2003 site>,
CN=Routing Groups,
CN=<Exchange 2000/2003 routing group>,
CN=Connections

CN=Configuration,
CN=Services,
CN=Microsoft Exchange,
CN=<Your Exchange Org>,
CN=Exchange Administrative Group (FYDIBOHF23SPDLT),
CN=Routing Groups,CN=Exchange Routing Group (DWBGZMFD01QNBJR),
CN=Connections

I'd suggest appending a 1 to the ones under the Exchange 2000/2003 routing group and a 2 to the ones under the Exchange 2007 routing group.

Back in Exchange Management Shell use Get-RoutingConnector to return the list of routing connectors.
Then use Remove-RoutingConnector and (when asked) specify the Identity as per the list. Repeat as necessary.

As for your second question, no, you don't need them any more if your legacy servers have gone. But are you sure that there are no mailboxes left homed on your old Exchange server. You can do a find in ADU+C for Exchange users with mailboxes and add the filter Exchange Home DB server with the name of the old server. Or you can check for legacy mailboxes under Exchange Management Console.

You may want to leave other references to the legacy Exchange server alone because you then have the option of building a legacy Exchange server back into the environment, say for example, if you needed to restore from an old backup.

Steve