For 2 contact so far, and one twice, we were both online, but we could see or speak to each other. I don't think this is Plus related since they do not have it, but I do and I didn't know were else to ask. Any hint what may have happened?

Usually when you add a contact you get to talk to them

I did speak with them before..

Occasionally there are server glitches (especially in the run-up to a new version of WLM) that mean you appear offline when in fact you aren't......I've experienced it myself on a few occasions.

If you think it's Messenger Plus! Live related then try uninstalling it and see if the problem keeps happening, but I'm 99% certain it's just a random glitch, especially as it's only happened a small number of times

it's not really a small number of time, it's always with a particular contact. We had to delete each other and add us back so we could see each other for a time