He writes that at first he bought an AT&T prepaid card on ebay and used iASign to get it working. After doing a little thinking (how would he top off the card, and wasn't a US phone number going to be pretty useless in the UK?), he popped the AT&T-branded US SIM out of his iPhone and put it into an old O2 XDA handset, which he brought to the Vodafone store.
At the store, he had them add the phone to his current Vodafone contract. When he returned home, he put the Vodafone-compliant AT&T SIM back into the iPhone, and used iASign to activate it. He reports that he's made a call using the Vodafone network although the iPhone itself still says AT&T in the corner. He's also confirmed that his Vodafone number is assigned to the phone. Visual voicemail is, sadly, a no go but SMS text messaging works fine.
Update: This post is causing quite an uproar over at the #iphone IRC channel. Participants there suggest this method should not have worked. SIM numbers are network specific and Vodafone should not have been able to use an AT&T SIM. Specific questions that remain are: How and why vodaphone accepted the AT&T SIM and "reprogrammed" it and how the network accepted a different CCID (thanks Spoonet). More as this develops.
Update 2: I asked another TUAW reader to try this in Canada. He writes: "Rogers wouldn't take the SIM card number since the network prefix wasn't for Rogers, i.e. 8930. Back to square one." One user, puescho, tried calling T-Mobile in Germany and was told that a technician said this was not possible.