A couple of questions first …
1. Are you getting an error when you try to send?
2. Are you getting emails bounced back to the sender?
3. Are the emails just sitting in the queues waiting?
Here is something to check on and this will cause you many problems with sending to certain domain.
A lot of companies have started using enhanced DNS resolution by doing a reverse look up on the sending domain to reduce the number of spam emails. If the server does not find a PTR record in the public DNS servers for your Exchange server that points to your domain then the SMTP connections are refused.
Get your ISP to setup a PTR record with the name of your Exchange server (ie. myexchangenetbiosname.mydomain.com)that points to your domain.
Keep us informed.