Transactional partially-ordered message queuing
A standard RDBMS should be enough; this is a sketch of how it can be done in a RDBMS even without BEGIN TRANSACTION capabilities (a mix of SQL/pseudocode):

Create two tables with the following columns:

Table MESSAGES:
*MSGID            int not null auto_increment,  (primary key)
SEQID             int,
SEQORDER          int not null auto_increment,
RETRIES           int default 0,
MSGDATA           varchar(...)

Table SEQUENCES 
*SEQID            int not null,  (primary key)
SEQLOCKED         int,
SEQHASH           varchar(256)


The Generators can simply insert into the MESSAGE table their requests (and optionally fill the SEQUENCES table):

For example suppose a Generator must insert a message with SEQID=120

1) INSERT INTO SEQUENCES VALUES (120, 0, MD5(RAND()) )
// if the SEQID is already present the previous query
// just fails, do not worry about it
2) INSERT INTO MESSAGES (SEQID, MSGDATA) VALUES (120, 'bla bla bla')
// the auto_increment option in columns will assign correct values for MSGID and
// SEQORDER


The Consumers can do their stuff without using BEGIN TRANSACTION in this way:

// retrieve the SEQID of an unlocked sequence that contains a message:
1) SELECT * FROM SEQUENCES s LEFT JOIN MESSAGES m ON  m.SEQID = s.SEQID 
      WHERE SEQLOCKED = 0
      ORDER BY SEQORD LIMIT 1
// suppose we retrieve a sequence with SEQID=120 and SEQHASH='102f...'
// we first lock the sequence using a standard tecnique:
2) newhash = MD5(RAND())
3) UPDATE SEQUENCES SET (SEQHASH=newhash, SEQLOCKED=1)
     WHERE (SEQID=120 AND SEQHASH='102f...')
4) IF (records_updated() = 1)   // lock acquired
   // we pick the older message of the sequence
   4.1) SELECT * FROM MESSAGES s WHERE SEQID=120 ORDER BY SEQORD LIMIT 1
   4.2) .... if we get a message (suppose MSGID=1234) then process it ....
   4.3) IF everything is ok THEN
          DELETE MESSAGES WHERE MSGID=1234
        ELSE
          UPDATE MESSAGES SET (RETRIES = RETRIES+1) WHERE MSGID=1234
   // finally we must unlock the sequence
   4.4) UPDATE SEQUENCES SET (SEQLOCKED=0) WHERE SEQID=120

restart from step 1)