It actually is how it worked in the beta at least. I've been using it for several months with my friends and the invite wouldn't work unless I had logged into steam on their pc previously.
That is certainly not the case, either something unexpected happened or either of you didn't have the families beta on. I have never logged in someone else's PC and neither have someone logged on mine, I always use Steam on beta and I was able to send family invites to my friends, however only the ones in my region (country) were able to join.
I did (and do) have the families beta on. Maybe that's the way it worked for some people? I don't know, but it certainly is what happened in my case.