Yes I did try that too, just forgot to mention it on my tried so far list. Thanks for the tip anyway.

Now I even tried downgrading phone ROM, Radio and protocol to a version that someone said to be working for him at another forum and that was said to be working in one of the "official" bmw phone compatibility lists here. ROM version was 1.56.405.5, Protocol 22.45.88.07 and Radio 1.27.12.11. Downgrade had no affect on the problem.