I don't know where you are located abotwright, but out here in California, by the time it gets to a termination, the employee has all but stopped coming into the office and burned the place down. From my perspective, taking credit for always firing the right person, is setting the bar really, really low. I'm much more impressed with a manager that manages to fire all the people that should, not that he should have fired the people he did.
For whatever reason, only the bottom 5% ever get fired. Where organizations tend to make the mistakes you are talking about is during layoffs, in which quite often, the wrong person is let go - but, in "theory" layoffs aren't performance related - though, in practice, they almost always are. Top Performers are almost never laid off, despite their role in the organization, and bottom performers somehow always turn out to be redundant. One exception to this is when a company drops a division or location - then it's across the board.