I'm a contractor in the UK and I get the "references first" request very often. I always say no. As far as I can tell this only happens when the agency doesn't have a real job and is just looking for corporate contacts to add to their rolodex.

My real beef with agencies is that they are yet another lossy filter in the process that goes:

Manager with role <-> HR Department <-> Agency <-> Jobserve <-> Me.

Neither the HR department nor the agency knows that Sybase and SQL Server are profoundly similar databases. The manager doesn't care - he wants a Java dev with some basic DB skills. But the hiring spec says "Sybase" so Sybase it must be.