I see. You put the word "European" in paraenthesis, that's why I thought you require the host to be European.
If you don't mind paying through US dollar, I have a recommendation for you. I personally outsource my email hosting to Balaji from Valai.net. He goes by the name MotleyFool on this forum. The rate is very reasonable, and the uptime and reliability has been excellent. (100% from what I can tell since my sign up 5 months ago). I will see if I can get him to contact you.
Don't you think you might get a few more offers if you post in the Requests and Offers forum? It seems if you have a credit card, you should be able to pay in any currency. I may easily be wrong, correct me if so.