First, remember that Reg E is not a court of law - you don't have to prove it beyond a reasonable doubt to deny a claim. It is nice when you can, but not necessary.
Second, definitely close out their accounts ASAP. You don't want these customers.
finally, I'd review your ATM deposit processes. Why are they able to W/D all that money before you get a chance to see that the envelopes are empty? Definitely follow Reg CC for holds on these deposits. We changed our system so that ATM deposits don't memo post at all. We have an employee get the deposits daily and they are manually run through by a teller. This particular approach may not work for your institution (depending on ATM locations, deposit volumes, etc.), but I would definitely review the entire process to see where you can eliminate some of these risks.