I got my recommenders unconventional gifts and they both were really happy with them.
Recommender #1 is currently taking time off to be a mom, with a consultant gig on the side. She often complained about how she had a really old version of Microsoft Office at home, which caused problems not only with providing me comments on my essays (she offered to review them for me) but also with her consulting job and simple tasks like sending out Christmas cards. I bought her a copy of the latest Microsoft Office with all the bells and whistles.
My other recommender has a huge sweet tooth and is the only man I know that watches "Cupcake Wars" on the Food Network. Well, he claims his wife forces him to watch it but his constant references to the show suggest otherwise haha. I researched the show and it turns out one of the judges owns a chain of cupcake stores - a branch of which is across the street from me. It was a no brainer - he got a box of Sprinkles cupcakes, the price of which makes you wonder if they're made of gold.
Bottomline: If you know your recommenders well enough, take a moment and think about your interactions with them over the last few months. It should be pretty clear what will make them happy.