There was obviously no ID card or computer database to check. What was stopping say, somebody in Nazareth in the year 1CE, moving from Judea to Gaul and assuming citizenship?
You would need a letter of reference from some authority like a prefect, which would be checked since citizens had voting rights. Also you would probably be under greater scrutiny if you obviously didn't come from Italy or Greece and your Latin/Greek was not really good.