A code of practice already exists for cold storage units - your job / your client's job is to make sure your service provider follows it.
Firstly, a risk assessment;
Physical Risks - low (I'm presuming your client stores boxed or contained product/raw materials)
Chemical Risks - low (get paperwork detailing that R22, R408A refrigerants are not used)
Microbiological Risks - low (again, presuming alarm based freezer systems, records on file that product is kept frozen - you may want to request random results)
Intrinsic Risks - low (again, presuming the cold store has an allergen policy and/or product is in sealed boxes).
These should all really be detailed in your coldstore's code of practice / contract / quality policy.
Secondly, test this;
Physical Risks - probably not relevant
Chemical Risks - hopefully not relevant (get the paperwork)
Microbiological Risks - stick a temperature tag on the odd pallet - in my experience, Irish cold stores are quite good at maintaining temperature, but have a history of leaving product standing on loading bays for quite a while (if your budget does not extend this far, google image a temperature tag, colour print it and stick it on the pallet wrap, really works a treat)
Intrinsic Risks - add to external auditing schedule and visit annually unannounced, for example, follow a delivery in, stick on a yellow jacket, smoke, swear, and generally act like a delivery driver and observe.
This not only allows you to fully validate you service supplier, but also gives you an opportunity to wear a yellow jacket, smoke and swear.