Hi Pete,
It depends on what portion of Lotus Notes you would like to sync.
I've got a "working" solution to sync email and calendar entries to my iPhone from a corporate Lotus Notes environment. I've gone through several iterations of this on
http://technobloggle.blogspot.com/
I am currently using VistoMobile to "push" the email from my Lotus Notes account to the iphone. It does keep the inbox in sync with the iphone using an IMAP interface for email and a desktop component installed on a connected workstation.
VistoMobile also has a corporate directory lookup capability. On the 2nd iteration of trying this it seems fairly stable.
Calendar entries are another story. I am forward calendar events in Notes to another email address. I am currently using Live Mail with the httpmail plug-in under Leopard. This allows fairly easy updates to iCal and also allows me access from behind the corporate fire wall. Entries that I add on the iPhone, I forward to the corporate account and import them into Notes.
As I said, "working" but certainly not ideal. Currently running 1.1.2 on the iPhone.
Frank