I tried out BluePhoneElite today and to my surprise it works with my original firmware P800! The manual even mentions the P800, saying that although you can initiate calls from the Mac - which will also have on-screen caller-ID - and have 'answer the phone' and 'ignore' options when the P800 rings, the SMS funcions will not work due to a firmware bug with all Series 60 and UIQ phones. A pity - something I would find very useful would be SMS composing on the Mac.
BluePhoneElite also has a slick proximity function. I particularly like the option to set your iChat status: