Your phone and Verizon are using CDMA technology. Most networks in Europe are GSM. It's a completely different network. Like using your TV to try to listen to a radio station.
There are a small number of phones, like the 8830 and I think the Storm, that can also be used overseas.
As for the SIM reference. AT&T and Tmobile are GSM so their phones can be used overseas with a different SIM, if unlocked and also if quad band. The GSM network frequencies in the US are different than in most of the world, so phones have to cover the 2 here and at least one of the overseas frequencies to work.