Are you running Leopard or Snow Leopard with the built-in firewall turned on? If no, then that's why you have never seen these messages.
Hooray! I thought I was the only one with this problem. I got the usual "we have never heard of this problem before" script from Applecare. Sometimes I wonder if it really is worthwhile paying for that service.
So reinstalling iTunes is the only way of fixing this problem? Seems a bit drastic....