In accordance with embodiments disclosed herein, there are provided methods, systems, and apparatuses including, for supporting transactional message handling in an on-demand service environment including, for example: enqueuing a message specifying a transaction to be processed via a host organization; inserting a row into a database of the host organization associating the message with a status of pending, wherein the row is autocommitted to the database upon insertion; updating the status for the row to ready if a commit operation for the transaction is initiated; requesting a lock on the row; and performing final processing for the transaction based on the status for the message and based further on whether the lock is obtained for the row. Final processing may include, for example, a transaction roll back, a transaction commit, a transaction requeue, a termination of transaction processing, or an orphaned transaction clean up.