If a Witch or a Wizard is Muggle-born they most certainly exist in a legal sense as Muggle citizens (i.e. they have birth records, school records, national insurance number, IDs and so on).
It is also not impossible that at least some half-bloods (the ones with one Muggle parent) have this kind of dual identity.
But what about pure-bloods and Wizard-borns in general? They are presumably born at St. Mungo's so that means no (Muggle) birth certificate, no citizenship and no ID (it also means no taxes now that I think about it :D). So, they are for all intents and purposes illegal immigrants.
I realize that most wizards have little to no contact with Muggle world if they can help it, but at least some of them (Arabella Figg - yes, she's a Squib but still an outsider) live there.
So what happens if a wizard (say upon entering the King's Cross) is stopped by a Police Officer and asked for an ID? Not everybody knows how to cast Obliviate or to Disapparate.