that's unusual i think. usually a month deposit as security, and first and last month's rent - at the most.
this credit rpt stuff is bullshit - i think they even use experian et al in the UK, which if true, makes one wonder why noone is looking at it
just slap them down in front of the internet and log on to mycreditrpt.com - pay the fee using visa - and show them your score etc, print it out, it's very self explanatory - after that there should be absolutely no reason for them to say theydon't have a credit history for you
you must be going with some large commercial leasing company. individual landlord's won't care to check provided you have a deposit and first month's rent