As an insider I can tell you that many companies have tried and/or are considering every one of these suggestions. That's not to take away from OP's point; the suggestions given are definitely out there for the average brand, and would set them apart.

Some examples:

KLM Surprise. "When passengers check in at KLM’s Foursquare locations, the KLM Surprise team finds out information about the passenger, then uses this to come up with a personalized gift to surprise the passenger with." http://surprise.klm.com/

Citi ThankYou Points. "Through a Facebook application, ThankYou members can combine points to make a charitable donations or choose from rewards. Citi says this gives members a chance to help their friends get a bigger reward or support a common cause." http://www.lowcards.com/share-citi-thankyou-rewards-with-fri...