UPDATE query is exected to use the existing index on (processing_node,
priority, date) both for WHERE and ORDER BY, as is expected from
EXPLAIN-ing the equivalent SELECT:

MariaDB [erp5]> explain select uid from message_queue WHERE processing_node=0 AND date <= '2013-06-06 22:22:49' ORDER BY priority, date LIMIT 1;
+------+-------------+---------------+------+----------------------------------------------------------+-------------------------------+---------+-------+-------+--------------------------+
| id   | select_type | table         | type | possible_keys                                            | key                           | key_len | ref   | rows  | Extra                    |
+------+-------------+---------------+------+----------------------------------------------------------+-------------------------------+---------+-------+-------+--------------------------+
|    1 | SIMPLE      | message_queue | ref  | processing_node_processing,processing_node_priority_date | processing_node_priority_date | 2       | const | 26622 | Using where; Using index |
+------+-------------+---------------+------+----------------------------------------------------------+-------------------------------+---------+-------+-------+--------------------------+

If it weren't using the index for ORDER BY, "Extra" would contain
"Using filesort".

Still, UPDATE behaves differently:

  # User@Host: user[user] @  [10.0.0.3]
  # Thread_id: 1635880  Schema: erp5  QC_hit: No
  # Query_time: 2.668405  Lock_time: 2.460698  Rows_sent: 0  Rows_examined: 49263
  # Full_scan: No  Full_join: No  Tmp_table: No  Tmp_table_on_disk: No
  # Filesort: Yes  Filesort_on_disk: No  Merge_passes: 0
  SET TIMESTAMP=1370557446;
  UPDATE
    message_queue
  SET
    processing_node=12
  WHERE
    processing_node=0
    AND DATE <= '2013-06-06 22:24:04'
    ORDER BY
    priority, DATE
  LIMIT 1;

So change the UPDATE..SELECT pattern into a SELECT FOR UPDATE..UPDATE
pattern, so SELECT's correct execution plan is used.