PS: Lord of the Rings was a movie it's not actually what we're about
I think there probably are isolated areas that are now seeing more people than they ever have but most locals don't get there either - DoC (the government conservation arm) is quite capable of closing places if required
The locals generally aren't travelling the country and pulling over into a picnic area when it gets dark, they're going there for a few hours and aren't as likely to need to poo, but it's their back yard.
Ideally we simply start building more public toilets, but the cost of that's going to fall on local property tax, there's no easy mechanism to separate enough money from tourists in vans to pay for this - our new government seems to be looking at an airport arrivals tax ($20 or something) to try and cover both this stuff and some of the costs of providing more protections in the National Parks, which the previous govt starved.
Meanwhile we fine people caught camping where they shouldn't and who make a mess, but about half skip out without paying them (from Monday's local paper)