Tagging every face... everywhere... and sending that data back to Facebook. That could be monumental.
For the very purpose of storing your opt-out preference, they would have to keep a record of your facial features, or you would continuously come up again as people tagged you manually.
Actually they already allow you to opt out of the facial recognition feature:
"Who sees tag suggestions when photos that look like you are uploaded?" ("Friends" or "No one")
You can also set Facebook to require manual review of friends' tags of you. I'm not sure if there's a way to completely opt out of being tagged though.
From an article I found,
* Shadow Profiles: Facebook is collecting data about people without their knowledge, using it to substitute existing profiles and to create profiles of non-users.
I know that this is mostly about facebook users, but seeing how much facebook spam I get trying to incite me to join in, I could totally see them go this route - Encourage people to tag friends who aren't on facebook and thus give those friends no other choice but to claim their identity.
It's unlikely they would enable facial recognition for non-Facebook users. How will they know the difference between two different people tagged as "John Doe" if they're not linked to a specific account?
This is an advantage? This is what you're willing to give up your privacy for?