Yes it does, I had the cybercabin service on AOS 1/20/02. It works great, and is a lot cheaper if you need to use email than using the .50/min service. Last year I spent 55.00 on Explorer to send about 5 emails!
How about the Legend? And do you mean unlimited access for the $100?
How hard is it to find internet cafe's in New Zealand and Australia? That would be cheaper, but not so convenient. My husband has a laptop for work, but I really hate to drag it along with everything else.