My data plan only allows email but not internet, could that be the reason?
Also, does Live Messenger require a data plan?
Yes, that is the reason. Google Maps has to have internet access to download its maps. It doesn't seem to care that it can get them thru wifi when wifi is available. It's not primarily a wifi application. That's easy to understand, since wifi would be intermittent while traveling.
I have not used Live Messenger, but I suspect it too requires a data plan for the same reason.