Your issue is not easily fixed by just switching over to Microsoft's Pocket PC, since all Pocket PC based PDAs are restricted to 64MB of internal memory – which may, or may not be more memory than what is already in your Sony Clie, depending on what model you use. The 64MB ceiling is a restriction of the OS platform, and not specification that the PDA manufactures get to override. To be a licensee of the Microsoft's Windows Mobile platform, manufactures need to build device that adhere to several performance thresholds - one of which is battery life. Since the memory in a Pocket PC needs a constant trickle of power to maintain the data it's holding, increasing the memory increases power consumption. By limiting Pocket PCs to 64MB of memory, Microsoft can better assure a certain level of performance.
If greater internal storage is what you are after, my advice is to look to the new Tungsten T5 from palmOne, which will be in general availability by the end of October 2004. The T5 has 256MB of internal storage. Best of all, it is all non-volatile storage. Anyone who has let the battery in their PDA drain completely knows that their device would now have as much data on it as it did when they opened it new out of the box. The T5 retains all its data and applications regardless of its battery charge. No other PDA currently available has this capability.