If I remove someone from my list and then add the same address again, will the contact receive "...wants to add you to his contact list" message?

Not unless they've also removed you from their contact list

If you're still in their contact list, then they won't receive an invite when you add them

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)