I've bought 3 phones from Ebay with no problems.
People get free phone upgrades that they don't want and then sell them on Ebay for less than half the price the handset would cost in the shops.
I think you could either get an Unlocked phone or one that's locked to Vodafone and your SIM should work.
Just search for Unlocked Phone and see what there is. Keep an eye on things for a couple of days and compare the price of the phones that appeal with, say, Carphone Warehouse for handset only model.
Here's an example: