In addition I recently had to cope with the hassles of setting up an H.323 connection (with ohphoneX) from behind a firewall at both ends and immediately concluded that people on any kind of wireless mesh that uses NAT are going to be severely limited since they aren't truly a part of the internet.
You are experiencing some of the issues of NATs. They work reasonably well in confined environments where the only thing behind them is a client with an external server. Putting the server behind the NAT, or a p2p application's peer, requires some magic in the firewall - eminently doable, but inflexible if it is managed by an IT organization other than you, and not the kind of thing a typical consumer wants to know anything about.
This is one of the best arguments for a global address space that doesn't require a life-support system (e.g. NAT) to maintain it, IMHO.
As to the massive multihoming issues that Strack comments on, and your reply, there are a set of considerations. If you want the network to have transit properties - if you want traffic from provider A to go to provider B across your network - you are offering the providers a transit service, and you might want to discuss with them what they might want to use it for. I suspect that the scaling and error properties of a wi-fi network will give them pause. If you want the network to multi-home to a variety of providers, it is not a transit network, it is an access network, which IMHO is a very reasonable way to use this kind of network.
Using it as ad hoc, I think you want to not relay route flaps to your providers. Rather, you want to advertise your prefix (however obtained) to them en mass, and handle the routing issues internally. This may mean providing wired connectivity between your various points of attachment to your providers, to mask the internal motion.