This has been our experience as well. We invested a lot of time and money in making sure Selenium tests run reliably for our clients. Despite this, the best reliability we managed to achieve was 90% with tests that run for 40 minutes, which is obviously not acceptable.
We have compiled a few tips we learned along the way in our blog post - http://novoit.eu/blog/05-5-tips-when-writing-Selenium-browse...