and, Jackie Chiles (“It’s outragious, preposterous, ridiculous”)
I used to love the Good Times episodes when ‘Sweet Daddy Williams’ made an appearance. He was a ghetto crimeboss who dressed like a black Liberace (full length furs, garish rings, etc.). I don’t think they ever said exactly what his business was- I’d assume he was a pimp or a drug dealer, but I guess they figured being more specific would have made him less comedic. (He was played by Teddy Williams who also played other characters in guest appearances on the show.)
Leslie Jordan always got a huge round of applause whenever he walked onto Will & Grace as Beverly Leslie. He said in one interview the character was actually supposed to be played by Joan Collins (!) but that she had to miss shooting for some reason or other at the last minute and he got the role because he was on the lot anyway and they rewrote the dialogue slightly (from a Karen counterpart rich-bitch to the world’s most openly closeted homo). There was one episode in which Karen and Leslie were supposed to go to bed together and have wild passionate sex in which it’s revealed Beverly really is straight, but both actors (Megan Mullally and Leslie Jordan) said “Oh puh-lease!” to the idea. (I actually felt sorry for his trolly little character in the final episode; it should have been Jack who fell to his death for taking the money and not putting out.)
Speaking of Newman, there was an episode of Seinfeld in which Elaine stumbled onto the bizarro Seinfeld group (Jerry and George and Kramer counterparts who were actually nice and not neurotic and read). At one time the door opens and a mailman enters and they greet each other in the “Jerry…” “Newman…” way except this Jerry and Newman then hug each other and are glad to see each other. I always thought it’d work better if they’d used Wayne Knight as the real Newman just to make it even more bizarro.
I love the unseen character of Howard Wollowitz’s mom on Big Bang Theory. (“DO YOU HAVE A GIRL IN THERE HOWARD!?!?!?!!?”) I’d like to see Laurie Metcalfe make a return as Sheldon’s mom though.
Another mom I wish would become a recurring character is Brett Butler as Joy’s mom on My Name is Earl. I didn’t like her on her own series (at least not after the show decided to address “real issues”) but she was hysterical as the “don’t you juuudge me!” gambling addict/hypochondriac/generally horrible mom de Joy and I’d rather see her return than Beau Bridges (who’s always good but doesn’t add much).
ETA: And if you can count a former cast member as a recurring character, I loved Steve’s return visits on Married With Children. The first was the best (when he climbs into bed with Marci and Jefferson because Al’s told them that she’s saved herself for him) but there were others. For a while he was a gung ho environmentalist then later a sportscar driving born again yuppie.
The Geek Trio on Buffy. Interesting how Warren, the most hated of the Big Bads, also has the lowest body count. I mean, y’know, compared to Angelus or the Master, not Jonathan.
Colm Meaney was never a regular on TNG; only on DS9.
Futurama: Zapp Brannigan, Lrrr, and (obviously) Morbo
WKRP: Bucky Dornster
Magnum P.I.: Mac, Buck Green, Lt. Tanaka
TNG: Commander Tomalak
Far and away the best recurring character on The West Wing was Ainsley Hayes.
I’d like to add Ethan from Lost. He’s appeared more after his death than when he was alive.
Wo Fat (Khigh Dheigh) from Hawaii 5-0.
ST:TNG: Q
Monk: That other OCD patient of his therapist, but I don’t know his name.
Frasier: Bebe, his utterly underhanded, cheating, lying agent.
Also Dale the Whale, who’s odd in that he’s been played by a different actor each time. He was originated by Adam Arkin, then taken over by a completely unrecognizable Tim Curry, and then another actor I’m not as familiar with. (For those who don’t watch Monk the character is a billionaire villain who’s bedbound due to morbid obesity so the actors play him with a lot of latex.)
Monk’s brother (John Turturro), the agoraphobic pack rat, has been on the show a couple of times as well.
Can we technically include Rik Mayal in The Black Adder since he made an appearance in every series of the show? I know that he played a different character each time, but the main characters also differed from one series to another.
Stuart Margolin’s hilarious Angel Martin on “The Rockford Files”. “I’ll stonewall 'em, Jimmy!”
Jack Riley’s equally hilarious Elliot Carlin on “The Bob Newhart Show.”
He also had a hilarious cameo as Elliot Carlin on Newhart. A therapist apologizes for his behavior and tells Dick “It’s taken me years to undo the damage done by some quack in Chicago.”
I liked Ainsley. I didn’t think of her because when she was on the show, she was actually on it in pretty much every episode. She didn’t exactly recur. Or am I misremembering? It’s been a few years.
Anyway, yeah, she’s fantastic. I love her reaction to meeting the president.
Ursula Buffet scores twice: Mad About You and Friends.
Not to mention Lt. “Broccoli” (Barkley). I always wondered how he ever qualified for a commission–lotsa fun to watch, tho’.
Oh, yes! I used to love that one guy that Belker kept busting–the one who used to give phony names while Belker was filling out the paperwork:
Belker: “Name?”
Suspect: “Curtis.”
Belker: “Last name!”
Suspect: “Interruptis!”
Belker: “Grrrrrrr!”
NYPD Blue also had several enjoyable recurring characters.
Chinese detective Harold Ng: *“When I first hear about this, I say, you gotta be kidding! Chinese afraid of police! Must be some scum-bag! But we kick his ass, huh Johnny?” *
Lowlife Steve Richards.
Detective Vince Gotelli (played by Carmine Caridi): “That was my tit cup!!”
And, from CSI:, the inimitable Lady Heather.
Actually, he played the same character, Lord Flashheart–just different generations (much like Blackadder), so it definitely qualifies.
And, off the subject of the OP for a bit, has anyone else seen a connection with Hugh Laurie’s three major characters?
Mad Prince Ludwig (German)
Prince George (German)
Lt. George (relatives in…wait for it…Germany!) 
I’ve just recently watched WW seasons 2 and 3 for the first time on DVD, and I believe that you are in fact mistaken - she was there for a decently long streak in her first arc, (appearing on the talk show with Sam, getting hired, first day, and so on,) and then would pop up more intermittently, when there was a plot function for her.
I loved the scene where Sam calls her back from vacation just because they need a prominent republican in the administration - and promotes her. 
The Monarch and Dr. Girlfriend on Venture Brothers. All the minor characters are pretty great, but an incompetent evil villain obsessed with butterflies, and his conniving and overprotective sidekick who looks like Jackie O and sounds like Harvey Feirstein?