I see and hear about it a lot. people come from overseas to walk one of the great walks, they either dont realise you have to book them to get on or they dont realise you need to book well in advance at certain times of the year, or they look online in advance and see loads of spare places and decide to make their decision about where and when they will walk when they get there, If you turn up at a doc office the day before you want to walk them in peak season, you're going to be out of luck the milford track books out months in advance, the only people getting on the track with late notice are the very few who get places from late cancellations or no shows... what then happens is they look around for other scenic tramps to do, and they usually end up doing tracks that don't require booking in the area, especially around fiordland and aspiring parks those other tracks are overflowing with people because of the scenario i described, you wont' be guaranteed a bunk or even a tent space at the small doc campsites, you wont even be guaranteed being able to sleep inside the hut it could be so full... or they end up on trips where the facilities are a lot less than they expect, basic huts that are too hot or too cold, no stoves. maybe no mattresses, or on very rough tracks that take good navigation skills to follow or even find which is what a good majority of the tracks in nz can be like.... the great walk tracks are the exception rather than the rule...
you can check availability and book here for DOC huts and campsites
note this is for the freedom walkers,
the guided walks are run independantly by private companies
A couple of pals of mine turned up to walk the Milford Track on spec, as 'freedom walkers', with diddy little packs, carrying hardly anything at all, and they had brilliant weather from start to finish.
Their experience differed hugely from almost anyone else I've ever met who walked the route, carrying massive packs in the pouring rain and having to make do with looking at postcards for the views!
Not my experience in 2006 and 2007 if you want to tent it. Some campsites I was the only one there. Didn't book any more than a couple of days in advance, some on the day I started walking Feb to April.
As far as navigation goes, I only used a map and compass once in 5 months when I ran out of little orange triangles to follow crossing from one valley to another in Arthur's Pass.
Wayne... no idea how they arranged their exit by boat... except that I know they did it that way. I'd ask them, except that they're currently on an extended exploration of India!