I've fired someone before, and I'd do it again. But it was a horrible experience; and I would want to avoid that kind of experience, especially for 3-6 months.
One thing that gave me a lot of confidence was to set up a peer review system. Once I saw that the group had the same instincts I had, it was a no brainer. (Peer reviews are so much more interesting on many levels, actually. I don't know why this never occurred to any of my bosses.)
Other than this, the "one week trial period" proposed in Rework (http://37signals.com/rework/) seems like a good way to avoid a "several month realization of uh-oh". Has anyone ever tried this out?