What's the most efficient way to batch UPDATE queries in MySQL?

Question

I'm writing an application that needs to flush out a large number of updates to the database for an extended period of time, and I've gotten stuck at how to optimize the query. Currently I'm using INSERT INTO ... VALUES (..), (..) ON DUPLICATE KEY UPDATE, which works to batch all of the values into one query, but executes excruciatingly slowly on large tables. I don't ever actually need to insert rows.

Other approaches I've seen are to update using SET value = CASE WHEN... (which would be hard to generate due to the way I'm building the queries, and I'm not sure about the performance of CASE for hundreds/thousands of keys), and simply multiple concatenated updates. Would either of these be faster than my current method?

It baffles me that, as far as I can tell, there's no idiomatic, efficient way to do this in MySQL. If there really isn't a way that's faster than ON DUPLICATE KEY, would it be worth it to switch to PostgreSQL and use its UPDATE FROM syntax?

Any other suggestions are also greatly appreciated!

Edit: here's one of the tables that gets updated frequently. I've removed column names due to them being irrelevant.

CREATE TABLE IF NOT EXISTS `table` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `a` bigint(20) unsigned NOT NULL DEFAULT '0',
  `b` bigint(20) unsigned NOT NULL DEFAULT '0',
  `c` enum('0','1','2') NOT NULL DEFAULT '0',
  `d` char(32) NOT NULL,
  -- trimmed --
  PRIMARY KEY (`id`),
  KEY `a` (`a`),
  KEY `b` (`b`),
  KEY `c` (`c`),
  KEY `d` (`d`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8;