My wife and daughter have learned to expect strange things when the unwrap their holiday presents. Clothes will never be in the boxes with the store from which they came, and they may not even be in a box at all. One of my wife's presents was in a rather attractive wood-tone vase, and another was inside a partially-filled tube of M&Ms (note that if you use this, the recipient may not open your present for days or even weeks).
But my best one this year was the copy of "Bullet in a Bible" that I gave my daughter (she didn't get to go the concert because of her young and impressionable mind, so this was the next best thing). I went to office depot, bought a ream of inkjet paper, took it home and carefully opened it (buy one with a paper wrapper if you do this, it will be much easier), extracted the paper, and proceeded to hollow-out an appropriately-sized section in the middle of the paper. Put the DVD in it, put it back in the outer wrapper, tape it shut, and wrap it up.
This was especially effective because it's not outside of the realm of possibility that I would give her a ream of paper. Perhaps I'll do that next year, and when she opens it, she'll just find... paper...
Have you done anything like this? Is there a website devoted to it?