Is it possible to have too much decoupling?
Not really, no. The only issue I can think of quickly would be inrush current on turn on (which can be a problem for e.g. USB peripherals) but this isn't too hard to deal with with a slow ramp up circuit.

Of course there's cost and board space, and if the circuit works fine and meets emissions regulations then adding extra capacitors isn't necessary.

Although they are a starting point, don't always assume the app notes are the final word on how to design your circuit - if it doesn't function as desired following their advice, then do it your own way. App note vary considerably in quality - some are generally reliable (e.g. LT, National Semiconductor, TI usually), and some app notes are pretty bad and contain mistakes, so always double check things.