I've worked with selenium for a couple of years. There are a fair number of gotchas, but it's definitely possible to write pretty deterministic tests. For one, retries of selenium actions are just necessary. So necessary, that you build them in to your test framework, instead of making them something that test-writers have to interact with.

I don't know what specific problems you were having, so I can't give more specific advice than that.