Gary Gygax was a huge fan of oblique homages, puns, and especially anagrams. A careful examination of the Dungeon Master's body of work makes this plain. The indefatigable Allan Grohe has cataloged many of these here. Over the years, I've indulged in the use of anagrams in my games. My contribution to Issue #2 of Fight On! is positively riddled with them, for example, as is the retro-stupid masterpiece, Encounter Critical. Consequently, I regard anagrams as part of the hobby's old school heritage and would like to encourage their use whenever possible.
To that end, the referee should grant a small but lasting boon to players who indulge in non-silly anagramming (unless your game is silly, in which case full speed ahead). For example, my friend Kevin once played an Elric wannabe named Nivek. The great thing about the name Nivek is that it worked; it sounded appropriate and, while it was an anagram, it didn't reveal itself unless you already knew something was up.
The boon should be something significant but not overwhelming and, most important of all, it shouldn't be game mechanical in nature. One of the big mistakes many contemporary games make is buying into the notion that the only way to reward a player is to give his character a +2 bonus here or extra skill points there. That is the road to hell. Instead, provide a specific in-game boon that is appropriate to the character, such as the fact that children instinctively trust him or that merchants never try to cheat him. Or whatever. The point is that the referee rewards the player for his clever use of an anagram by giving the character some little extra bit of personality/background that's beneficial to him in his adventuring career in a small way. A similar approach could be applied in games where the referee wants to encourage punning or allusions or whatever.
And if you have trouble coming up with anagrams, here's a nifty little webpage to help you out.