One thing we started doing about a month ago is using
http://www.hallmark.com to send out e-cards to all of our birthday people. We just wish them a happy birthday. If they used to be regulars and now they're not we say we miss them, and if they never were regulars then we encourage them to drop back by.
I haven't really noticed it working yet but it certainly can't hurt. Seems like you have quite a few people though, not sure if this is practical for you.