MX & A DNS records

I have been using a external web site to handle all my pop email, but recently I have set up an exchange server. My problem is, My hosting company allows modify the MX record but do not allow me to set an A record. How do I forward email to my Exchange server. My exchange server can only be accessed via IP and not by a FQDN. Example

Website
mysite.com Resolve to 99.88.777.1234

Exchange site
exchange.11.222.33.444

The Ip address is delivered via DHCp from my ISP, however I've had the same IP address for over 2 years now.

Current MX rcord point to:
Mail.mysite.com Resolve to 99.88.777.1234

if I can only change the MX record how will the mail reach my exchange server since it won't resolve to a listed IP?

What kind of hosting company doesn't let you change your A records?

Anyway, you could get one of those quick-update dynamic DNS addresses like from dyndns.org and similar places. Then, run it on your mail server, and point your MX record to it.

i.e., You set up the dynamic DNS client to be foo.dyndns.org. Then, you point your MX entry for qux.com to foo.dyndns.org. Then, mail for qux.com goes to foo.dyndns.org, which happens to be your mail server.

Colin