Deny Access (instead of 404) for non-existant user accounts
I would try setting up a conditional redirect from your 404 page to your custom users-specific error page, that only fires if the path of the referrer is user/*.

I would try to do this using Rules.