I have been having this issue for a long time on my rooted Droid 3 using the ROM it came with and this happens daily with relevant logs being left or any clear trigger.
Basically what happens, and it tends to happen after the phone has been on for a few hours, I will send a message, usually with Handcent SMS (though I've experimented and tried other apps including the stock SMS, still happens) and occassionally a text will get stuck.
Now one of two things generally will happen. Either it'll sit "sending" for about 5 minutes before finally failing. This acts like a text bottle neck, because if, say, I have a multi-page text being sent, the other queued messages will send instantly when the initial text fails.
The other thing is that the text message will just sit sending indefinitely until I notice it hasn't sent and I delete it manually. If I resend it, sometimes those subsequent attempts will also hang.
And once this starts happening, it will continue to happen until I restart my phone, resulting in my restarting my phone several times a day.
An interesting observation that could help diagnose is the issue is once when I observed this happening, I open up a SQLite debug app and when I try to open up the mmssms.db file, it cannot read the file, which makes me think, perhaps the file is locked which is why the SMS process cannot commit the change to the database. Just an idea; don't know if that's at all related.
Edit: This does seem to happen more often after heavy usage, say playing a game. Could it be that' some sort of SMS-handling daemon gets killed, perhaps?