I would suggest, since you indicate you are attempting to set a 'policy' or 'procedure' for future soon-to-be-ex-employees, make it both a corporate and a personal going away.
Decide on a standard going away corporate award. Perhaps as suggested, visit an award shop, and choose a simple wall plaque. Make it as expensive as you can easily budget in, figuring that this is not an everyday, or every month, occurrence. If your business is photo-genic, such as in a building or something, or if you have a sign or anything, you might consider making a photo the normal gift. I work for a government agency, and our building, which houses the agency (and only the one) has an official photo and that is used.
That takes care of the "official" part. Now comes the personal. For this, you either need know the individual (or have a contact who does, supervisor, coworker, etc) or make it generic. We would all like personal/personalized over generic any day. If your worker was an avid gamer, buy him a gift card expressly for his system (XBox, etc). Goes to the movies alot? A movie pack. Etc. If she is in to hiking, perhaps a card to a local outdoor shop.
A previous answerer commented on how bad gift cards are. I disagree. Buying a thing, ties the person into that thing. Buying a gift card, as long as it is personalized, enables the person to realize they were cared for, yet choose the thing themselves.
This personal gift doesn't have to be large, even a $20 card is useful. In our organization, all monies left over after the lunch we all contribute to is turned in to a card.
Being that the worker was with you for so long (unusual, under normal turnover circumstances) and appears to have been close to you, doing this personal part shouldn't be an obstacle. Doing the 'corporate' part as well, enables you to re-use this as a 'process' for the future.