get an actual .eu VPS host (often which charge deceptively by making you pay euro's... 5 euro's is a friggin lot..) which most times don't even do native ipv6 (you sign up for a tunnel to get ipv6 instead, same as any .us host), in which case you're limited to the location of your ipv6 tunnels location
OR... the easier way, get the cheapest Xen VPS you can find, like I have the cheapest plan at VPSLink for like 7-8 a month and its great, and sign up at www.tunnelbroker.net BUT when it asks you for closest endpoint, choose a european IPv6 location instead.. You can choose from Brussels, Germany, Japan, etc. and then all of your ipv6 traffic will appear to be from that region
Otherwise; if you insist on having a true european ipv4 server host, try chaotic-hosting.com, my friend runs it and will cut you a deal but you might have to communicate by e-mail first.
Goscomb Technologies - offer native IPv6 in London, UK with a /96 per shared IP address on a /64 network.
I have a VPS from them just for the sake of the native IPv6 and I must say, I am highly impressed! (even if it is a tad expensive)
OVH - also has a native IPv6 enabled network in both France and the UK; however due to their custom kernel I am unsure whether they support IPv6 on their VPS/RPS's.
Leaseweb - apparently have native IPv6 transit, hosted in the Netherlands and use Globalcrossing, Tiscali and Hurricane Electric as peers; however I'd probably contact them prior to purchase for further discussion.
BudgetDedicated - hosted in Amsterdam, Holland have native IPv6 with a large number peerings.