The regulations are addressed to the "operator of a Web site or online service directed to children, or any operator that has actual knowledge that it is collecting or maintaining personal information from a child". If you have an enforced policy of banning those under 13, you gain "actual knowledge" of the status of the liar when yuo learn their age. The FTC addresses the lying child question in FAQ 14, saying
The Rule does not require operators to ask the age of visitors.
However, an operator of a general audience site or service that
chooses to screen its users for age in a neutral fashion may rely on
the age information its users enter, even if that age information is
not accurate. In some circumstances, this may mean that children are
able to register on a site or service in violation of the operator’s
Terms of Service. If, however, the operator later determines that a
particular user is a child under age 13, COPPA’s notice and parental
consent requirements will be triggered.
If a banned lying child claims to now be 13 but in fact is still not 13, the notice and consent requirements have been triggered and you can be (massively) punished. If the child is over 13, there will be no penalty, since you didn't violate the rule.
The rule does not include any standards for proving age, and you have to evaluate any such evidence at your own risk. Whatever proof you would require, that would (if it were reasonably related to proof of age) constitute personal information, and the regulations require you to "obtain verifiable parental consent prior to any collection, use, and/or disclosure of personal information from children". In other words, parental consent is necessary to get the information necessary (birth certificate for example) to establish that parental consent is not necessary. You are strictly liable for violating the rule if you actually know that a user is under 13, and you can't argue "But he showed me a birth certificate".
§312.5 gives details about what constitutes "verifiable parental consent". (c) Exceptions to prior parental consent says that you can obtain personal information for the purpose of obtaining parental consent (otherwise, you would never be able to ask for parental consent, since you can't ask "who are your parents"). (c)(6) allows "collecting a child's name and online contact information to... take precautions against liability", but that does not include e.g. collecting a child's birth certificate. In other words, the only apparently safe course of action in case you have obtained actual knowledge that a user is a child is to require parental consent.