It sounds like your companies Exchange Servers are not setup for this. In order for the mail, calendar, and contacts apps in SL to work with your companies MS Exchange servers, your company has to be using at least MS Exchange 2007 with SP1 Security Roll-Up 4...
Since Exchange 2010 is coming in a short while, some companies decided to skip the upgrade from 2003 to 2007. Since this was more of a rip and replace then it was an upgrade.
The reason it works with the iPhone and MS Exchange 2003 is precisely because it is using the MS ActiveSync protocol which is very different from what the mail app would use to talk to the same servers.
As to the other issues where the company is running Exchange 2007 but you still can not use it without first logging into the companies VPN.. It sounds like either the company is not using an exchange border server to provide HTTPS access to mail. In other words, your company does not provide web based access to e-mail from the internet.
If it does, then you should enter that servers name into the mail app settings. Then, theoretically, it should find the rest of what it needs and setup normally.
I have done this with my companies Exchange servers and it seems to be working perfectly.