I can't say that I've heard of VidaHost, I can however only recommend these guys:
Meebox, a danish hosting company. Never had any issues, downtime is extremely rare and always announced well ahead. Support is excellent, and pretty much available 24/7. They're cheap as chips as well, in case you grow tired of problems.. These guys are definitely the way to go.