A lot of people complain about 2 things with the PICAXE's - speed and storage. Recently, the topic came up for an interpreter for an externaa eeprom and eventually evolved into using PIC24's and dsPIC's.
Why don't you just type a simple interpreter in BASIC (i.e. read eeprom, jump to function...