You can always import an iphone from the states via one or other website, this is what I did. Perhaps you can even now from the uk or via ebay should work as well.
I bought mine locked at firmware 1.1.1 and unlocked it myself but for a hundred dollars extra or so you can buy one unlocked and ready for use.
So you just need to pop the sim card in there when it arrives and you can start phoning !
(rereads text... I sound like a commercial !)
Visual voicemail won't work, but as I've never used it I am not missing it. SMS works, not MMS. Edge Data connecion works fine for me.
As for when it arrives in Europe/Denmark, which was your original question,
Politiken.Dk says
in 2008... but that was written in July 2007 it seems.
I think you have a choice - either import an unlocked one from elsewhere or wait till mid-2008 at least...
🙁