Funny. I've had lots of problems with Hays. Cancelling cheques, unenforceable and ridiculous clauses in contracts for example.

The best agencies? None. Don't use them if you can help it. If you have to the smaller the boutique ones tend to be better, if nothing else because they'll have the better clients and more interesting projects.