Hi obragblog. Sorry for not responding to your question. I was transported back to the Stone Age for a couple of days there when my computer went and died on me. Just three days, but I'd already begun wearing furs and building stone circles in the back garden by the time I got it fixed...
Anyway, I run W3 Total Cache on my own sites and I've never known it to interfere with the plugin, so I don't think that's the problem. As far as I know, there's no reason any caching plugin should interfere, as they should only be caching front end pages, not backend stuff like revisions that are never publicly displayed on the site.
I suspect the problem in this case was the sheer number of revisions that had built up in your database. The plugin doesn't interface with the database directly; instead it uses WordPress's get_posts() function to grab all the revision copies from the database, then deletes them using another standard WordPress function, wp_delete_post().
Using WordPress's own functionality like this is a safe way to delete stuff from the database, but thinking about it now, this approach will probably fall down when it's confronted by literally tens of thousands of revision posts. In a case like yours, it's much more efficient to interface with the database directly and delete the revisions with a SQL command like you did.
It is amazing how quickly the revisions can build up - I usually manage to generate at least 20 for every post I write, correcting typos and the like. There should be a default limit in place - hopefully there will be in some future WP release.
I'm going to look at the plugin code again and hopefully rewrite it to cope with cases like yours, so the next update should deal with this issue. Thanks for pointing it out - and apologies again for not responding sooner.