Well facebook can recognize your friends right now, so I would think if you give them a couple of hours they could find a match on a random photo. Provided that photo has actual face
Sure, but recognizing a picture of one of your friends is a matter of searching O(100) people. Recognizing a picture of any Facebook user is a matter of searching O(100 million) people. It's a totally different problem, and there's no reason to think Facebook, which hasn't solved the smaller problem perfectly, could solve the larger problem at all.
Our daughter is 2. I recently dropped some photos of her into iPhoto and told it who she was with about 20 of them. I have probably 60gigs of photos in its library, mostly of people. More recently I loaded my wife's pregnancy US scan into iPhoto, including some stills from the 4D scan. iPhoto popped up a message asking if this was my daughter.