You’ve got a pretty serious problem if you cant send messages to one another on the LAN on same mailserver.
Standard Troubleshooting steps:
1) Open ESM and verify the database is mounted
2) Check all the server application event logs for anything obviously wrong (there must be)
3) Check the queues to see where mail is queuing and perhaps track a message.
4) Turn up the level of logging on the exchange server’s diagnostic logging tab in ESM. This will log more detail to the application event log which might clue you in to a more obscure problem.
Are outlook clients receiving any errors when they connect (or try to) the exchange/SBS server?
What was the application that was installed by the vendor that you think broke mail? SMTP covers internet mail but outlook clients on the same server won’t use SMTP so they should be two different problems unless the exchange software or more basic stuff like DNS is screwed.