Ok, figured that very few people actually have to use Lotus Notes

So, I solved the problem myself.
Commontime has a free 30-day trial for mNotes Desktop and Wireless, and so proceeded to install the software. This is one application where you MUST read the installation instructions as it is fairly detailed for both on the PC and in the phone. Follow the instructions exactly (which was what I did) and you're on your way.
Verdict - super smooth and seamless synchronisation between your Lotus Notes server and phone, via your PC. Sync happens almost immediately in the background when you plug in your phone - Calendar, Contacts, Email (last 7 days), Journals. If you activated the Wireless option during install, you can even sync via your cellular data link (unlimited data plan advisable), and new mail gets pushed to you too!
One caveat is that your PC needs to be connected to the Lotus Notes server if you want to receive updates, if you're using a laptop, then perhaps the Desktop version will serve you better.