Right, now it's working although I'm not 100% sure why...
First I created a host file entry for the server again just for luck.
Second I edited the registry as per these
instructions however the correct server name was already there.
I changed the server name in the registry from being server.domain.local to just being server - this didn't work so I changed it back to server.domain.local (With correct server name obviously) and restarted the BES services again. This time the Messaging connected! I looked in the MAGT logs in the BES folder and could see everything was OK - weird eh!
Now a reboot of the server could perhaps of fixed this but as it's SBS I can't reboot in the day (Standalone BES is very nice for that reason!) so perhaps me changing the registry then restarting the server just kind of jogged something into life.
So to any other 5305 sufferers the problem is definitely in the BES not seeing Exchange even though it's on the same box and has DNS pointing to itself etc etc. Could be a bug there for RIM to look at as this product is designed to be installed on SBS servers (Or at least is a supported configuration)
Also just to give credit I found the last post in this
thread by Aribrown to be helpful in me getting to the resolution.
Now I'm nervous that next time the server is rebooted the Messaging Agent will bomb out again... (Crosses fingers)