I already tried to pull out the battery and many switch on/off of the network.
The diagnostic is the following:
Instant email (through BES) --> OK
Blackberry browser --> KO
Google maps, BbMaps --> KO
Vodafone Live (Kind of Bberry browser pointing to Vodafone Live) --> OK (After accessing the Vodafone Live portal I can access some website)
I already check with the BES admin and they don't block anything as part of the policy.
In summary, I have a partial data connection, the missing part is the APN.
Blackberry Storm 9500 - Vodafone UK