Ive been with eukhost probably 6 years now ? I started with Host Heaven (Rob can tell when he set it up), and yes there is probs, up and downs but not so many downs with the servers. Every company will have downtime, its unavoidable. Its one of the cheapest places youre going to find, but service isnt cheap. I dont know of any Hosting companies that allow free Skype to their centers for support, its usually email only.
I currently host 7
website hostings and am doing a 8th real soon hopefully.