Format the phone. Backup all data and charge the battery fully. Then switch off the phone and disconnect from the charger (it will not work otherwise).
Now the hard part. Hold down the green button, the star key (*) and the three key (3). Keep the buttons depressed and power on the phone. Keep the buttons depressed until the screen comes up with Formatting. Wait for it to finish, and voila, factory clean phone.
Unless nokia allowed vodaphone to mess with the firmware, your phone should be clean now.