What they should do is mail something (a verification code) to the residency address the user provided, with instructions to access a particular webpage to verify.
Well, that's what Moneybookers also does for example.
Though it does not prove that the user lives there, but NOTHING can prove that the user lives there. Not even paying bills prove anything - anyway in many places bills are in the name of the building owner, who can own many buildings and not even live in most of them, but rent them out. Then the landlord can verify a plethora of addresses where he does not live, and his tenants can't verify anything.
But the letter with a code proves something which is actually the only reasonably needed thing: that the user can receive mail there, so a letter from the court or lawsuit can be delivered to the user there as valid.
If the user lives there or not is actually irrelevant, because nothing can prove that, besides maybe attaching a GPS device the the users leg with constant monitoring at MtGox headquarters. That would be something MagicalTux would need! LOL! He wants to have up-to-date users location, as the "utility bill" has to be not older then 3 months. Why 3 months? I can "live" (i.e. sleep?) somewhere today, and never appear there again, GPS monitoring of users should be a must "to fight money laundering".
Oh, and there is another thing to ensure with even more certainty that the current users "residence" is known: when the user is in jail, preferably for many years. Then a copy of his jail sentence could be sent to MtGox, and level 2 AML verification will be grated for the period of his jail term. Not longer of course, as then the user will move out! In fact it would be best for MagicalTux's users-tracking requirements, that only jailed users will have verified accounts, all accounts of other users will be frozen, and they will be instructed to commit something that will land them in jail, so they can deliver a notarized copy of the jail sentence with address of the jail. Only then MagicalTux will be sure that none of his users are "money laundering". Anything else is ineffective.