As the ISP-provided modem was generating pretty weak WiFi signal I've disabled its WiFi function, bought an Apple AirPort Extreme and connected it's WAN port to the modem. Now everything works just perfectly, but the AirPort configuration utility keeps complaining (yes, I know how to turn it off, but I am curious) about double NAT and demands me to reconfigure the modem to bridge mode. Why should I? What problems can double NAT cause?
Anything that automagically open up holes in your firewall (for instance, as BitTorrent client might use uPNP to get a port opened for itself without direct user intervention) is going to fail, because it can't access the 'outer' NAT.
Otherwise, it's a bit of added latency (not likely to be significant) and you're paying to power two devices instead of one.
I had tried double and triple NAT-ing setups for fun. For most intents and purposes, double NAT-ing doesn't affect simple browsing/mail experiences. (adds less than 1ms of latency)
However, if you want remotely access your home network (or services) from internet. It would be a lot more complicated to set that up. That's the only disadvantage I can think of.
One major problem would be that with Double Nat'ing you also create 2 private networks.
Private Network 1: You did turn off the Provider's WiFi, but are potentially with your in-house wiring still attached to the Provider supplied router.
Private Network 2: Your own WiFi Router, which is also wired to the Provider supplied router, will have again it's own network setup for anything attached to the wired ports, or WiFi.
Assuming that this will all work well, Devices on Private Network 2 might consider devices on Private Network 1 to be on another network (based on the network mask provided).
This appears to be the case for my Remote App on my iPhone for my Wired Receiver not wanting to connect to the receiver, although I can actually Airplay to it. Once I connect to the Providers Wifi with my iPhone (Private Network 1) - then the remote app also works.
Problems arise mainly because the NAT tables on one device fill up or lose track of a particular connection, this type of configuration will cause issues with peer-to-peer technologies that are unable to effectively trace back the network path, MTU path discovery may not function or break and gaming/media services that use uPnP probably will not work unless reforwarding these services manually. [Source]
I see nothing wrong with double NAT except (as you've noticed) that an Apple Airport router device will complain about it. There may also be some applications (games for one) that may have trouble with double NATing. I used double NAT on my airport device and I told it not to bug me with double-NAT warnings. Everything I do works fine. I do not notice any slowdown. I have a web server, an SMTP server and both work fine. Besides that I do regular browsing, ftp'ing, etc. I wish I could tell my airport to warn me about problems, but to not consider double NATing a problem.