Right.. when you remove it, you don't remove your email from the list of your contact... In fact there is the option that say if you want to block it, because it continued to see you online...
In fact, they won't receive that message unless they've deleted you from their Reverse List. (That's the list that can be found under Options => Privacy tab)