I use Linux Mint on my office and home PC's and I have a company-issued Palm Treo 750 running Windows Mobile 6. Here's what I did to easily (and for free) get all this to work perfectly...
* Moved all mail accounts to Gmail, including main work account
* Moved Calendar to Google as well. (I really like Gmail and Google. I could write a post entirely about this alone)
* Cut office and use Google Docs for all but the really heavily formatted docs originally designed in MS Office
* Added Gmail on the Palm Treo as a POP email account - WM6 auto-configured Gmail (sweet) so now work emails are visible on the phone's inbox
* Signed up for Plaxo online account at http://www.plaxo.com/
* Synchronized my Google calendar with Plaxo online http://help.plaxo.com/al/12/1/article.asp?aid=1093&tab=search&bt=4n
* Downloaded Plaxo for Windows Mobile http://help.plaxo.com/al/12/1/article.asp?aid=1545&tab=search&bt=4n
(This says it's a premium service but it is now free as well
). This will sync contacts and calendars with Plaxo, which in turn is synced with Google. This puts your Google calendar on your Today Screen (main screen) in WM along with your emails.
So at this point, you would have email, contacts, and calendar all working on ANY computer ANYWHERE you are, including your phone. With the added benefit that all your contacts and your calendar are automatically backed up. This really saved me last week when I accidentally deleted all my contacts from my Treo!
All this leaves is then is tasks. If you go the free route (like me) there is no way to sync WM / Outlook tasks. So what I did was create an account at http://www.rememberthemilk.com
. You can read about it here: http://www.rememberthemilk.com/about/
I also added the remember the milk Gmail Firefox plugin from here: http://www.rememberthemilk.com/services/gmail/addon/#install
. It's awesome.
The only downside to my system is that to see tasks on my mobile phone I have to go to m.rememberthemilk.com. They will not auto-sync to Windows Mobile tasks. If this is a must have, rememberthemilk does offer a premium service that adds task sync to Windows Mobile and BlackBerry. You can find it here: http://www.rememberthemilk.com/services/milksync/
It took me a while to get all this together but it's really simple to set up and use. Hope this helps some of you - It certainly caused me to drop yet another thing that many people cling to windows for.
Addendum: By moving to Google, I also have access on my phone to every doc, spreadsheet, and presentation without taking a bit of storage on my phone, and without document syncing issues. For notes (since you mentioned notes) Google Notebook is where mine are kept. Again, all accessible from my Palm's Internet Explorer on my homepage at igoogle.com.