Thank you for the help and suggestions.
We have decided to go with EuroVPS after the high recommendations received in this forum.
We are very happy with our decision.
Here is the low down of our experience so far:
1. Very capable and friendly support staff.
2. Competitive pricing.
3. Were able to meet our needs exactly, by offering us a solution that they had already discontinued but were able to commission to meet our needs.
4. Fast website connectivity, certainly faster than the shared hosting we were using from the States.
5. Close to our time zone (2 hours behind), so the pre-sales discussions were possible without any problems.
I am really glad that this website exists. Trying to find an honest independent hosting review website seemed an impossible task. Google certainly gives results, but the resulting websites are filled with self-serving unverifiable drivel. If it wasn't for this website, we would not even know that companies like EuroVPS or HostDime exist.