Re: At 7 bytes per stored phone number
My 2005 Moto RAZR could store numbers on the flash memory in the SIM card.
That's a standard piece of SIM card functionality. My 1995 Nokia could do it, and my current Android phone can do the same. It's not something I've ever felt the need to do on Android, though.
The SIM card is more limited in the details it can store for each contact, though, IIRC you are limited to one number (and no other fields) per contact name, and the name is limited in length and stored in upper-case only. Hardly ideal.