I can 'see where they're coming' from but I think that the agency has adopted an over-strict interpretation of the rules.
Some agencies used to add 'holiday pay' directly onto an employee's regular pay. For example if the employee was working for £6 per hour, instead of 'banking' about 65p of holiday pay for every hour worked, they'd simply pay them £6.65 per hour instead. That meant that the employee would effectively lose their right to a 'real' paid holiday because, if they requested one they'd simply be (correctly) told that "you've already had the money in your weekly pay packets".
So now 'banking' of holiday pay (rather than including it in weekly pay) is a statutory requirement. However, if an employee now takes a holiday after, say, 20 weeks of employment I can see nothing in the rules which prevents the agency from giving him 19 weeks accrued holiday pay before he starts that holiday. I can understand why they wouldn't be able to give him the 20th week of holiday pay at that time, as they'd have failed to 'bank' the money in accordance with the rules.
Chris