>I guess in most companies this would be a no-brainer, but we're a small outfit with a focus on personal development, intrinsic motivation, good climate, and low turnover. Do you think there is any way to rescue this situation? Or should we make this (perhaps justifiably, after their misleading self-presentation) the first time we let someone go for performance reasons?

You have to fire. No hiring process is 100%. It is worse to have them stay. If your organization is unable to fire people because you have 'not firing people' as an objective, you're optimizing for things that aren't advancing the business, and essentially shooting yourselves in the foot.