Shoutbox

First, make sure you both are using the 'Video Call' feature, not the 'Webcam chat' feature.

This because the webcam feature has been removed from the latest version of Messenger. And if you happen to use the webcam feature , the contact will not recieve any invitation eventhough it seems so from your side (if you're using an older version of Messenger).

Second, it also sounds that both your webcams aren't configured completely properly in Messenger.