I'd first talk to the HR department at the job you are after to see what their requirements are and if there are options / other alternatives you can suggest e.g. a personal reference in lieu of this one. Otherwise, can you not talk to the last place you temped at through the agency for the reference, as another option?
It's a matter of raising the issue and working through alternatives to find a reasonable resolution.
I do find it amazing that they would need references from every workplace. I think it would be impossible for a lot of people. Some work places I have been at refuse to give references, other than to confirm employment during X period. Also, people move and people die. How could one find them for a reference for what one did X years ago?