If you are seeing access denied 5031 errors sourced from the MSExchangeTransport service like the one below, make sure the "Network Service" account has been given the rights to the TransportRoles folder. The "couldn't delete routing table log file E:\TransportRoles\Logs\Routing\RoutingConfig.." and "UnauthorizedAccessException Access to the path" errors give a pretty strong hint that there is a permissions issue causing the errors.
The MSExchangeTransport service is started with the "Network Service" identity and hence the account needs to be provided access to the TransportRoles (typically "c:\Program Files\Microsoft\Exchange Server\V14\TransportRoles") folder to create and update queue and logging folders and files. The default permissions assigned to the "Network Service" on a vanilla installation of Exchange Server 2010 can be seen below:
The problem that occurred in this particular situation was the queue and log files had been moved from the original Exchange installation location, using a combination of the Set-TransportServer cmdlet and adjusting the EdgeTransport.exe.config file. The "Network Service" identity needed to be granted access to the new log/queue location "E:\TransportRoles".
The technet complete set of steps required to move the Transport folders including the permissions required are documented in the "Change the Location of the Queue Database".
Another way to move the Transport files is to use the Move-TransportDatabase.ps1 script included in the "C:\Program Files\Microsoft\Exchange Server\V14\Scripts" location included with the Exchange installation. This script configures the required ACLs for "Network Service" as part of the move.
Have fun messaging