Hi:
If I understand your post correctly, you had been pairing for two months and it suddenly stopped? Sure sounds like something was updated, perhaps without your knowledge. With all the computerization and over the air connections, maybe BMW did a software upgrade.
Did you try deleting the car as a "Trusted Device" (I am assuming it was set up that way originally) and then try reinstalling from scratch? Bluetooth with the Treo can be hit or miss, but since you had it working perhaps a setting got corrupted or something like that.
I find it almost laughable that BMW claims they never heard of a Treo or funnier yet, they never heard of Palm!!!! I wonder if they heard of Mercedes Benz or Microsoft?? Maybe they just keep the employees locked in a room with no outside contact.
Seriously, let us know how it goes.
SteveTaz