I would assume you have already tried to "Shutdown Queue" from the Queue Status screen in SL? If you have tried this already and the record is still locked I would try shutting down the db in the evening when no-one is using it and run the Crash Recovery utility on it. This will unlock all processes and records, etc.
I have done this before (shutdown, run Crash Recovery) with quick success. Depends on how quickly and easily you can shutdown the db. In a "pinch" I do not know how to fix this issue while the db is still live...
Darren