Hi markmaya! Welcome to Nokia Discussion Boards!!
I guess you are not mentioning about send SMS from a JAVA or C++ app, but from the default phone's Messaging option, right ?
Have you tried sending SMS using the same sim in a different phone and also different sim in your N91?
If possible please try to back up all 150 messages to your PC, and try sending SMS with no previous SMS on phone.
Also please make sure that you are in full network coverage area and you are not trying to send SMS in peak time when networks are clogged!
Just my blind thoughts,

Give a try and send in your results!
BTW, In my N90 if its taking some time to send SMS, what I am doing is just pressing the menu button and could navigate through the phone menu, where sending SMS will be doing in the background. Will that be working for you ?
Regards
Gopal