The keys are not stored on the phone alone.  It stores the key on a microSD smart card.  (Actually, it uses a split key system, which requires both the phone and the SD card to recover the key-- which is even safer-- you can read about it here: http://www.othercoin.com/OtherCoin.pdf )