I've remembered another example - Lara Means from Millennium season two. I really loved this character and how she intereacted with Frank. Her story did come to a conclusion, and a good one at that, I just wish she could have stuck around for longer.
It was an excellent send-off, but it still kinda irks me that his stand-in was the rather bland Megan Russert. All of the original cast were awesome. Kellerman was the last Homicide character I really liked.Pretty much every character who leaves Homicide: Life on the Street? Keeping in mind that I've finished the first four season only so far. I swear, after the pilot, Crocetti was my favorite character. At least they gave him a proper send-off, even if Joe Polito wasn't involved.