Was there a reason that these guys hadn't gone through the process to file for a patent themselves, even as a defensive mechanism? I suppose their suggestion that there was a lot of prior art would have made that a non-starter for them as well. Anyone that suggests that software patents are good for innovation is clearly naive.
You would definitely want an experienced patent litigation attorney and a small team.
I think they should have responded and called the bluff - I don't think Google would pursuit it far