Your post immediately made me imagine a go-between that enabled people to send a physical/voucher gift to an email address or social media account. Sender would choose something and pay for it, but assign the recipient as a virtual address. The recipient would then hit the go-between and arrange fulfillment, choosing the postal address themselves.

If you could get it tied into the networks and built up as something of a tradition within Facebook/Twitter /Pinterest (as you said, Facebook would be perfect for it), it could get some traction.

Maybe have it trawl recent posts for gift suggestions in various price brackets.