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: Galaxy Note 3 and LG F6: 5 lines, 1x $15 5GB data, 2x $5 Android web, 1x $2.99 T-Zones, corp discount + $10/mo loyalty discount = $93/mo tax inclusive
Secondary: iPhone 4 & Optimus Dynamic II: TracFone (Verizon); Galaxy Epic: RingPlus (Sprint)
Tablet: iPad Mini Retina w/ T-Mobile 4G LTE