Maybe the interviewers were just really good judges of character and skill (I think I probably was a good fit for the position), but it was hard to look past the fact that I didn't think I'd proven that I fit the role to them.

It's also possible that they are simply willing to fire people who are incompetent and prove to have lied about their accomplishments. If that's the case, it shouldn't be necessary for you to "prove" your skill, which is much, much harder to evaluate than most interviewers think.