"We wound up just deciding that we should play it to the click, speed up the pauses just a bit. It takes away a little personality but keeps the song tight."

I wouldn't have done that, in though it's a massive pain I would have used the tools in the DAW to change the timing to match the song, and not the other way around.