I and a friend both have Serenes and they both do what you are explaining. I have also brought it up with my dealer in sydney and they cannot find a fix. I also think that they are deleting numbers from my 6000 at home as numbers that used to be in the 6000 phonebook are now gone.
It is interesting that it does not add +61 to every number and many will not dial at all with this prefix. I am constantly editing numbers so that I can actually ring them (which is a pain on the run) only to find out that when it is docked at home the phone adds the prefix again.
We looked at the demo Serene in the shop and it was adding the same prefix.
This is such a pain that it is making the phones virtually unusable. (My friend is just as annoyed as I am and being a first B&O purchase for him, he really doubts the brand is up to it's reputation!)
I have actually contemplated dumping the phone and going back to my old Nokia.
I will be interested in a solution.