[tlrobinson]

No, they just have to store the fact that you don't want your account to be tagged in other people's photos. Of course that doesn't stop people from tagging as your name (not linked to your account) or a variation of it, but that's a losing battle.

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.

[personlurking]

I believe Max Schrems, that young Austrian guy (who asked for the info FB had on him and received over 1,200 pages worth) told the press later about Facebook's 'shadow profiles'.

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.

[coreygoodie]

Even if they don't tag you (as in, it showing up publicly), FB can still store whether or not you're there.