I think it's a know-your-audience thing... Some people would be really charmed to have to work to obtain their gift (concrete, ice, maze, etc.), some really wouldn't. If you feel they've "resorted" to gift cards and don't really enjoy the gifting process that much, they may just rather the gift card be handed to them inside something simple, like an envelope, tiny stocking, or tin (if inside anything at all). Actually I've noticed that a lot of places would like to sell you things specifically to hold gift cards, like a stuffed animal holding a wallet-like pocket you could slip the card into.
I do like the idea of bundling the gift card with something small related to the store/potential use--I think the standard idea is a Starbucks card inside a Starbucks mug, perhaps along with a couple of packaged Starbucks treats like biscotti sticks. Or a keychain with a bicycle on it, coupled with the Kmart card in a small box.
I think small, flat boxes and tins; fun drawstring bags; folding Chinese food-type containers; etc. are generally readily available at, say, a large craft store. You could always fill them with candy, confetti, etc. around the gift card.
My grandfather used to give us cash tucked inside various pages of a crossword puzzle book (kind of like the gift card in the fashion mag idea). I would recommend mentioning that the card is in there, so watch out for it, rather than leaving it as a surprise, because it may fall out accidentally or get thrown away with all those cards that seem to fall out of magazines. (experience)
