The Zaurus line of PDAs have been using Persistent Storage (although they don't call it that, they just call it flash memory) since the SL-5600 model.
I wouldn't use a PDA that didn't offer this, if I have to soft reset the machine or remove the batteries for some reason (have a couple of spares for long trips
) then I expect my data to still be there afterwards.
Can't remeber when exaclty the SL-5600 came out, but it was late 2003 or early 2004, good to see MS finaly catching up
Stu