Dequeue not yet committed message

Someone correct me if I'm wrong, but I don't think what you want to do is possible.  Once a message is in the queue, you either commit and save all the enqueued messages, or rollback and save none.  So you probably need logic that will not enqueue the message with the specific key in the first place.

Or, this may be a good case for a GLOBAL TEMPORARY TABLE.  Instead of queuing your messages, INSERT them into the table.  When you need to delete one, just delete it from the table.  When you are ready to commit, loop through the table, queue the messages that are still there, then commit.

Forgot that procedure was there, thanks, Mike.

Dmitrii:  If the amount of data to be queued isn't a lot ("a lot" being a relative term) then you might skip the temporary table and just add the messages to a PL/SQL collection (TABLE OF payload type), then you can use a bulk enqueue as Mike suggests to enqueue the whole table at once.  Define the table in a package body to give it session scope.  But if the amount is large enough to have an impact on memory used, then use the table, BULK COLLECT into a collection when you read the table, and enqueue it block by block.