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.
Which is why I think we don't have too many examples of this happening. Only a select few would go to the point of trolling, and that's partly the reason why I usually leave these sort of reports, so that other moderators will be able to take a look, and judge for themselves.
I suspect this sort of thing has been attempted, but I suppose the attitude to it was; don't say you've previously been banned, if you don't want to risk your account. I like to be on the more cautious side, and take a look at it, whereas I know there will be several others who won't think twice.
The thing is, from the way I handle these instances, it would likely be ineffective the majority of the time. Since, as you say the majority are likely bragging, and telling the truth about being banned. So, as some would say, my over cautious approach is likely 99% inefficient most of the time. Though, having it left in the queue, its likely it'll be handled regardless.
The thing is; the majority of the time these users that are admitting to being banned, have already broken some other sort of rule too since they don't really care about how things run here. If they've been banned before, and continue to post here its likely they won't change their behaviour, and be banned whether or not they admit to being banned anyway.