Jim has gotten a lot of the layout done, but we're having trouble finding a cheap enclosure. Because the board will have connectors on 4 sides (and quite big ones at that), the standard enclosures are too deep. They would require channels cut in all 4 sides. We think we need a clamshell-style, screw-together case.
You're doing it the wrong way round.
First find a ready-made case, with as few preconceptions about shape/size as possible, then design the PCB to fit. The PCB is by far the easiest and cheapest thing to customise. Look at as many manufacturers' catalogues as possible (this is where paper catalogues really score!) - it is likely that a few will jump out as possibles.
Don't think "I need to find a case to fit my PCB" but "That's a nice/cheap/cool case, can I fit my product into it?"
Be flexible in connector types - horizontal/vertical etc. Consider IDC types with ribbon & headers to the PCB, e.g. to stack vertically on a panel.
If there are a lot of complex cutouts, think about using a PCB as a panel, as it can be cut and printed with minimal tooling costs, and you may be able to include it on your main PCB panelisation.
You can even include snap-out sections for optional connectors.
If you need to get machined holes, try to get them all on the same face - this will cut costs.