I looked at my own S390g. Looks like you exhausted every possible avenue - the phone is supposed to automatically switch over to phone memory after the SIM card memory is full for SMS. The last two options I can think of, are first to remove the battery while the phone is on; then, put it back in after 30 seconds and boot the phone up. That always clears up some random problems on phones both new and old. Secondly, you would have to just erase all the SMS and start again. You probably are trying to avoid that or you would have done it already.
Castrol EDGE 5W-30 is my drug of choice.
Primary: iPhone 6 64GB, Galaxy Note 3, Galaxy Avant: 5 lines, 3x $5 Android web, 1x $2.99 T-Zones, corp discount + $10/mo loyalty discount = $93/mo tax inclusive
Secondary: Galaxy S3 LTE & iPhone 4S: TracFone (Verizon)
Mobile Broadband: HP Stream 13 w/ T-Mobile 4G & iPad Mini Retina w/ T-Mobile 4G LTE ($10/mo for 5GB with hotspot)