By contractual issues I assume you have a set of plans and specs that call for PID control, undoubtedly written by a process/civil engineer who has never commissioned a control system in his life. Ah yes - the wonder of shelf specs. I have come to the conclusion that a great many programmers and engineers think that "PID" is synonymous with "analog control", even though that is not really the case.
You and Peter are correct - you can make PID work, although it can be somewhat painful. Refinements to the PID algorithm such as tolerance can improve your odds, and very low gain will also help. Nonetheless, even the textbooks will state that PID is not suitable for slow response systems.
One trick I have used in similar circumstnces is to provide two operator selectable algorithms. The specs probably do not say you can provide only PID. I basically provide two subroutines. One implements PID, one implements logic similar to my description above. The operator can switch to the one that works best. Set up both, demonstrate both at the acceptance test, and then let the operator decide. You comply with the contract documents, the system will work, the engineer will have his spec met, and everyone will be happy. Something to consider if you get too frustrated tuning the PID at commissioning.