That's interesting. If that's their only verification, you could probably pretty easily get one of those rechargeable or "gift card" credit cards, and plug in any address you want.
You might need to get European cards, though, and I'm not sure how they work over there or how easy they are to get.
They end up working just about the same though. You can buy them both at a retail store for cash, and use them just like a credit card anywhere Visa/Amex/Discover/whatever is accepted.