Well, I have checked their web site and everything seems to be on the level. They charge decent prices for what they offer, they say they started in September 2003 and they don't lie about it (domain whois shows sept 2003 as registration time).
Overall, my impression was that the individuals running the service have the strong will to build a big venture out of CybexHost. The only thing that I find not normal is they calling themselves as CEO/owner and Vice President. First of all, to be a CEO, the company has to have a shareholders agreement. I doubt they do. Also, if you have a Vice President, then there has got to be a President.
I would say go ahead and try them, but don't forget to report back with your experience.
thanks for the opinion, I think I am going to try them out as soon as I talk to them via email, I asked them some standard pre-sale questions, see how quick the response is and what they have to say and then we'll see.