Other ways to reduce:
Limit frame rate where possible (some scenes may only need 1-2fps, some may be fine with 10-15fps, etc. - there's probably no reason ALL cameras need to run full-out).
More careful motion masking (block out things like windows, streets in the backgrounds, monitors or flashing signs in the field of view, etc.) - extraneous things that will trigger unnecessary recording.
If your network is solid, you could try increasing i-frame interval.
Use VBR, so bandwidth will drop with less contrasty/complex scenes and less motion.
If client insists on constant record on some or all channels, try setting a low constant framerate and kick to higher rates on motion (assuming cameras and/or VMS support this).
Of course, all suggestions above (yours included) rely on convincing the client to go with what's *necessary* rather than what they think they want...