I can see the mailbox sizes through the server and this is smaller than the actual amount in the mailboxes in outlook!
Unless you see steady growth, this really doesn't mean anything. Exchange supports deleted item retention (default is 7 days, IIRC) so what you see at the client isn't really all items in the mailbox.
Also, generally speaking, mail isn't stored by outlook (exceptions being "offline" mode in versions of OL older than 2003, and "cached exchange mode" in OL2003) but is stored on the exchange server. Outlook makes a MAPI connection to the server and displays the data locally.
Reviewing the situion: You made a change to the router (and "remote access" on the server... I am guessing this is ISA?) now your users cannot receive email. The evidence does not point at either Outlook or Exchange, but at the changes you just made.
Easy test: attempt a manual connection to your exchange box
from the WAN side of your router.
Code:
telnet <the address listed in your MX record> 25
HELO example.com
MAIL FROM: user@example.com
RCPT TO: <local email address>
DATA
<some text>
QUIT
After the first command, you should receive output along the lines of
220 <your host name> Microsoft ESMTP MAIL Service, Version: <some version> ready at <date, time, timezone>
If not, it's a network issue. Now try from the LAN side. If this works, you know your problem is almost certainly with your router. If not, you screwed up the configuration on the server. In either case, roll back your changes--you both knew what you were doing
and took notes, right? If the answer to either of those questions is no, you've learned several important lessons, I think...
If indeed you can talk to the exchange box and mail is successfully delivered to your store, you should probably seek help in one of the MS Exchange forums on this site (there are three, I think--pick the appropriate one for your Exchange version.)