I'm not a lawyer, but in my opinion this is a case of mis-selling. Nowhere in the product advertising material does Orange mention that a core feature of the iPhone is missing. Visual Voicemail isn't a third party app, it's a core feature of the phone, which has been advertised by Apple from day one of marketing. I was told by four individuals working for Orange that staff had been given training in which they were told that no feature of the iPhone has been tampered with or changed. Orange staff were not told that an important feature was missing.
I complained about the situation and made clear the case at my local Orange store and after 4 days of escalating the complaint to senior sales managers, Orange has given me the option to cancel my contract without any charge. The store manager did mention, however, that Orange intend to have Visual Voicemail up and running in Jan. 2010, but so far I haven't been given a guarantee.