Don't have a Treo, but I use outlook for mail on two different computers (a desktop and a laptop), and need to maintain mail & folder structure on them both.
My solution was to have Outlook leave the messages on the server on both copies of Outlook, as well as delete messages after a certain periood of time (7 days for me, you may need more or less) on the desktop only. basically, I have to download mail on each computer at least once a week, which is a no-brainer for me. Also, if I'm travelling and only using the laptop, mail won't get purged off the server until I connect from teh dekstop when I get back home.
I have no idea if that solution will transfer to your Treo, but it works for me.