Setting up Exchange with Domain on webhost

Once exchange is up, change the MX record for the domain to point to you rpublic IP (web host has to do this).. then redirect SMTP on your firewall to the local IP of your Exchange server. You can also use a DMZ, but it's not required.

You can leave the DNS for your domain intact, except for one change - that's the MX (mail) record.
you'll probably want to ask your ISP / webhost to setup an 'A' record (i.e. mailgate.yourdomain.com) and point the MX (mail) record at that A record.
You'll then need to configure your firewall to route incoming SMTP (port 25) at the internal (or DMZ) address of your exchange server which is confirgured for an SMTP connection.

MX records work on a priority basis.. tou can leave any existing MX records in place as long as they're lower priority (i.e. a higher number) than the new SMTP one. You can then configure exchange to collect POP mail as a backup to the SMTP.. just incase your internet connection fails.. that way mail'll be backed up at your webhost / isp / mailhost..

hope it's clear!

Please don't forget to enable reverse lookup on your domain name by having whomever controls the IP address space to put an PTR record in.    For instance, if your Exchange server's name (see properties of virtual SMTP server) is "mail.mydomain.com" and the real (outside) IP that it uses to deliver email is 10.9.8.7, then a PTR record needs to be put in assigning that relationship.  Then when an SMTP server that requires reverse lookup is talked to by your email server, it will go out and ask who 10.9.8.7 is, and your ISP will return "mail.mydomain.com", and compare that to what your email server says that it is, and when it matches, will allow your email.

Ok, so I get the basic concept on how to setup the incoming but when it comes to sending out mail should I setup the Mail Relay in Exchange to point to the web server's SMTP server?

Well, if I understand correctly, you are trying to replace the web mail part with your interna; server.  So, the way that Exchange SMTP works is that it tries to send outbound email directly to the destination.  That is, for an email address to someone at hotmail.com, your SMTP server does a DNS lookup (via its configured DNS) for the MX record for the domain "hotmail.com" and an IP address is offered in response.  You can emulate this yourself by going to the command prompt, type "nslookup" and enter, and then type "set type=mx" enter, and then "hotmail.com" enter.  
Other domains are done the same way.  After getting the IP of the MX record (Mail Exchanger for the domain) your SMTP server establish an SMTP protcol session to that IP address to give them the outbound email.
Within the SMTP properties of the virtual server you can set a "Smart Host" which tells your SMTP server to always send outbound email to one specific SMTP server (your ISP, for instance).  Most SMTP server will refuse to relay your outbound email (as they are for someone else domain, not theirs).  If you negotiate this with your ISP, or an SMTP filtering service (like Message Labs) they will configure to accept email from YOU, for anyone else.  The rare time you would use this would probably be to send all outbound email to be filtered by a service like Message Labs.  Otherwise, going directly with the MX record (as described) is more fault tolerant and robust.

Gotcha, that makes sense.

So I've got the SMTP issue squared away but now let's say I want the clients to have access to the OWA. Basically all I have to do is open a hole in the router for port 80 and 443 (SSL) to point to the Exchange server and then have the web host create a Host Record (A) mail.mycompany.com which redirects to my server, is this assumption correct?

Yes, that should work.  After you get it to work, then you fcan get an inexpensive cert so that SSL will work without the error.

GoDaddy does £17 certificates IIRC.

but PLEASE, PLEASE, PLEASE ensure that all of your security is tied down, before opening up ports.. as you will get attacked from this interface. Keep an eye on event log for failed (hack) logins externally etc (Event ID 529 in your event logs).

Turn on password lockout, disable guest, ensure passwords are all secure and preferably standard named accounts aren't accessible.

How did you get on?
just to recap, assuming I've understood OK.. just as a simple, standard exchange setup:
1) setup your new Exchange server to accept SMTP connections and test internally
2) open port 25 (SMTP) on your firewall JUST to the internal IP address of the server and test from externally - using (possibly) telnet 25 to see if you get a response from your server at your external IP address
3) Configure Exchange to send via a) a 'SmartHost'.. usually your ISP's SMTP server, or b) Directly, via the DNS (ie. it looks up other SMTP servers using the internet DNS itsself and delivers directly there (this is the usual way of doing it, but you may want to use option 1 as a stepping stone).
4) When you're sure Exchange is working OK to send/recieve, ask your ISP to change your MX record (that's just the mail record portion of your domain's DNS .. completey separate from the www record) to point at your exchange server's new external IP address. In practice, this will be an 'A' record for a name like mail.example.com and the MX record pointing to the A record.
5) Bingo

So.. at it's most basic, this should be your answer. Let me know if I've misunderstood your aims?