I've had problems with security checks too, basically cause no-one at the company you used to work for cares about you getting it!
It might be good if you've had lots of temp jobs to put it down as one job with the temp company for the entire range of dates rather than each individual place you went to.
Same with education - make it cover all you're holiday dates unless they specifically ask you not too, or the education establishment will not provide it.
I can only echo Mercenary Pilot's sentiments that it does 'little to deter real evil doers and only discriminate against honest people'.
As with most things, a little 'creative paperwork' can save you a hell of alot of trouble.