h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

Why, buy them Biscuits, of course. Oh, so they may have some already: but they're bound only to be the soggy, crumbly, broken and plain-flavoured ones left at the bottom of the barrel.
Either that or just give them some book tokens.

Well, I know one of these people that "has everything." I had to deal with this problem just a couple of days ago. And I finally decided to get him...a toy. Not just any toy, but a voice recognition-powered attack robot! It can take directions to move up to 50 feet at a time and shoot missiles and all sorts of other groovy stuff. And what, you may say, if he already has one? Pit them against one another in a little robo-war! Mwahahahahaha! The more the merrier!

Well, you can get the person who has everything many things...
just not the things that only one of will do.
Gag gifts work well.
If they have hats, they may not have that one that says 'Damn Seagulls'
and looks as if they played you for target practice.

Or get them a bowling pin.
A toilet seat. (one of the nice cushy ones.)

If all else fails, give them money to buy what they want.
If they have everything, they can buy more of the 'everything' they want.