Get a phone that allows you to store a decent number of messages.
(start rant)
With the low prices of RAM, it's unforgiveable for phones to still only be able to store 20 or so messages.
If each message is 160 characters, that's 160 bytes per message. Call it 200 for the sender info. Times 20, that's a mere 4 kb. A 512 kb storage chip should cost about 5p to the phone manufacturer in today's markets. (512MB flash cards, 1000 times larger, are available for £5 in highstreet stores)
My current phone (t-mobile vario ii) has more or less no limit on messages - I've had over 2000 messages in its memory before. When I lost it for a little while, I brought a temporary replacement for £20 new from woolworths, and was shocked to find it only stored 20 messages or so. In a new phone in 2007! Even the startup animated graphic on the phone took far more than 4 kb, and I could choose between several different startup animations. What's the point? Put that memory into message storage!
(end rant...)