I tried to get verified with bitmarket.eu using the ebay method, they told me to send them a message from my account, but their account was no longer active. And still a week later no one has done anything about it.
I was planning on making a sevice to exchange coins for moneybookers but havn't got around to it yet as i have other projects on the go at the moment.
Would be interesting if you got around to creating one eventually.
I find MB to be the best mainstream payment processor.
They offer many deposit/withdraw methods as well as a very cheap debit MasterCard, instantly funded by your MB account balance & usable at ATM's or stores.
Chargebacks are also much harder than with PP.
Low fees, too.