Technically, wouldn't you be employed via the staffing agency? I remember working nearly 2 years for Manpower and was issued employment checks by them and I claimed that I worked for them.
Now through employment verification, you may run into problems if the agency tells the lender that you only worked for 16 months of the past 2 yrs, for example. However, if you were employed for a long duration then it can easily be proven via pay stubs (keep 'em).