Initially I was skeptical about running games with the gestalt rules or with fewer than four players, but a couple months back my next door neighbor bought Gamesmastery D1: Crown of the Kobold King and offered to run it for myself and his roomate. We had a high pointbuy to work with, gestalt rules, and action points (since this was being set in Eberron), and we went through the adventure with only moderate difficulty. So long as you have the ability to disable traps, inflict damage reliably, and heal between combats (even with a wand) a pair of gestalted characters can do well for themselves. Since you have fewer actions, combats tend to last longer, which means that both players and monsters get more opportunities to show off their various tricks and use more creative tactics.
My only concern with small gestalt parties in the long run is that loot may become an issue. Giving out half the loot for half as many PCs might be a bit too stingy, but giving two PCs the loot expected for a four man party could be excessive after a couple adventures, expecially if your PCs are the types to take everything that isn't nailed down.
Robert "Overpowered on Paper, but Awesome in Practice" Ranting