To resolve the issue you need to:
- Stop the Microsoft Exchange Transport service.
- Rename the folder called 'data' to 'dataOLD' under the location C:\Program Files\Microsoft\Exchange Server\V14\TransportRoles
- Start the Transport service
- Make sure a new folder called data has been created
You should now be able to telnet to port 25 internally and externally and mail will start to flow again.