Have you check with
http://www.ccbilleu.com
or do they not have a store system. You might want to also check into
http://www.2checkout.com/
I'm not sure if they take European clients.
http://www.nikrobilling.com
I know they take European clients and have a store system. They are pretty expensive is the only problem.