I haven't had the need to send SMS messages to any of my website users, but perhaps this might help...
It would depend on whether the carrier is available, but most carriers have an email gateway available you can email a SMS message to which is relayed to the phone # provided. You could potentially reduce the number of SMS messages that need to be sent through a third party gateway drastically enough that the month cost for the remaining messages is negligible. If you could sent 3.5k of the 4k SMS's via a carrier gateway, you could get 500 messages/month from a 3rd party provider for < $100 year
Just a thought... not sure if you are aware of that or not. Sorry I can't help with any experience with specific bulk gateways
http://en.wikipedia.org/wiki/List_of_SMS_gateways