Unless they were making some post that gave a credible statement that they were banned in error, I'd just nuke the account and not even think twice about it-- especially if they appeared to be acting abusively w/ the new account.

This is a forum, not a court of law.  Unjust bans don't deprive people of their freedom or their life (particularly people who've demonstrated that they're willing and able to evade a ban).  False confessions are a thing, sure, and I wouldn't be completely shocked if a couple people saying they were banned were just trying to sound cool... but I think it's no major loss to lose a user who thinks saying they were banned makes them cool.  If they would eventually grow into a good participant, better that they do it from an account that doesn't have the boat anchor of bragging about being banned in their very first posts.

I don't see any cause to investigate in any depth.  If someone admits to breaking the rules we should feel comfortable taking their word for it.  Perhaps if they didn't behave abusively with the new account we shouldn't hold it further against them -- just nuke it and move on.

Most likely, though-- these people were actually banned.  Excessive exposure to internet crackhouses like reddit and twitter where bragging that you were banned while posting violent harassment usually won't get you banned again unless you blunder into also offending the politics of the corporate overloads just has people thinking they can get away with saying crap like that.