If you are running Exchange 2007 and you are getting the above error message from users outside your organization there is a very simple fix.
Set-ReceiveConnector -identity "Default [SERVERNAME]" -maxmessagesize 20MB
That will double your receive limit from the internet. Now if you want to go bigger you could do:
Set-ReceiveConnector -identity "Default [SERVERNAME]" -maxmessagesize 1GB
but that is not recommened at all.
The available options for the size are: B (bytes), KB (kilobytes), MB (megabytes), & GB (gigabytes). The maximum you can do is 2GB and any unqualified sizes are treated as bytes.
If there are other options you want to change with your Receive Connectors check out Set-ReceiveConnector on TechNet.