Have had my iPhone 3G and 2006 M5 paired for just about a year no - with no real issues (except synching the contacts list which SCOOPZ helped solve).
Last week, I turned the car on and it had one of its "moments" where it just decided not to find the phone and also wasn't in it's "paired list". I've found in the past when this happens, I can force it to connect by manually making a call from the phone. However, this time that trick did not work. Frustrated, I unpaired the phone and tried to repair but to no avail. I've been trying off and on for the last 3-4 days and I'm really starting to pull my hair out.
I've turned off wi-fi, 3G, location services, data roaming...nada.
I've turned the phone off and on so many times I can't count.
I've even tried pairing my wife's iPhone 3G and that won't work either.
All this suggest that it is the car that is having issues (not the phone) because both our phones pair fine with the Toyota minivan and BT headsets.
The one clue I think I might have is that in the I-Drive menu for Bluetooth Settings there is a checkbox for "Bluetooth communications active" - and the box IS checked. However, what's odd is that I cannot "uncheck" it and then check it again...what would seem to me to be the equivalent of "rebooting the BT stack" in the car. I have a feeling that if I could accomplish this, the issue would be resolved.