Let's break this down.
> I'm convinced that unit tests don't usually find bugs.
They don't, they test whether or not the API contract the developer had in mind is still valid or not.
> IMO, most bugs are edge cases that were an oversight in the design. If the dev didn't handle the case in code they're not going to know to test for it.
You don't write test to find bugs (in 98% of cases), but you can write tests for bugs found.
> Fuzzing is a much better approach.
If you're writing an I/O intense thing, such as a JSON parser, then yes. For 80% which is CRUD, probably not.
> The project with high code coverage is basically shit and has so many bugs that we regularly cull anything marked less than "medium" severity as "not worth fixing". This project was written by a team that loves "patterns", so you can find all sorts of gems like Aspect Based Programming, CQRS, N-tier, etc. well mixed into a featureless grey Java EE goo. We get so many bug reports that its someones job to go through them.
You are blaming tests for bad design choices. With the patterns raised unit tests only get you so far, integration tests are what help you prevent bad deployments.
> The other project with no tests is a dream to work on. Not a single file over a few hundreds lines, everything linted and well documented. Almost no methods that don't fit on the screen, no recursion. No bullshit "layering" or "patterns". I can't remember the last time we had a bug report, since our monitoring picks up any exception client and server side. Every bug I've worked on was identified by our monitoring and fixed before anyone noticed.
So how many exceptions were raised due to bad deploys? Core review only gets you so far.
> If your developers are great then tests would hardly fail and be fairly useless, and if they're terrible tests don't save you.
Failing tests don't have to do with devs being "great" or not. Developers must have the capability of quickly testing the system without manual work, in order to be more effective and ship new features faster. If the tests are one-sided (only unit tests, only integration tests), then this will get you only so far, but it still get's you that far.
Don't abandon good development practices only because you saw a terrible Java EE application.