1. There are two types of internal memory - 64Mb of DRAM and 128Mb Flash... the former is used to run apps (and is what you typically run low on) and the latter is used as filestore (I'd be surprised if anyone has filled this yet). If it were possible to upgrade this memory, of the two I would suggest upgrading the 64Mb DRAM as you will get no benefit from upgrading the filestore at this point (other than the ability to store more apps of course).

These guys will upgrade the memory chips in various iPAQs - might be worth contacting them to see if they'd be interested in looking at the Nokia 770? Although it has to be said they're not cheap - $370 to go from 64Mb to 256Mb, that's the cost of another 770!!! - and while I haven't used them myself (I'm in the UK and would have to ship my iPAQ HX4700 to the US and back) they come recommended.

Edit: I've just discovered that expansys.co.uk is a UK upgrader I'll contact PPC and ask about their ability to upgrade the 770 - purely out of interest at this stage, as I'm not convinced there is a need for more memory right now (the last firmware improved things a lot, though I still run low on memory eventually).

2. Seems like pretty much any RS-MMC is acceptable - mine is a 1Gb SanDisk and works just fine.