Just to update you, I have now been doing some extensive testing, but just a correction on the steps you set out above. Once User A has created and sent the appointment it closes down. So the appointment is not open when user B accepts. User A only updates once receiving the 1st acceptance.
In my testing one of the users has a BB account. In that scenario I was able to re-produce each time. I then disable redirection for that user on the BES and I am now no longer able to re-produce the problem. So this leaves me wondering about things like the CDO.dll etc.. do you think that is at all a possibility?
Thanks for your comprehensive answers, I think your tag is absolutely right!