I happen to agree that exceptions should be left to exceptional events—something entirely outside the scope of the algorithm—and not something that seems well within the purview of the task at hand. For example, when validating data sets, which is something it sounds like your code does, detecting and handling an invalid datum sounds like the code's raison d'etre. An exception here would be ridiculous.
Another example might be a parser of some sort (for example, in the compiler itself). If it detects an error in the input, that's not an exception. It's a well defined state transition in the parser. Exception handling is not error handling in the general sense. It's only for errors for which the right course of action isn't even knowable except perhaps a couple levels up, and is unlikely to happen much in practice.
For example, if you have data structures that automatically resize to fit whatever your program needs, and you hit an OOM situation, what then? There's likely to be no good way forward. You want to unwind far enough that you can leave things in as consistent a state as possible, and otherwise probably just crash with a hopefully-useful error message. Depending on the nature of the program, "crash" could mean widely different things here. If it's a command-line program or a restartable system service, "error message and exit" is probably the best thing. If it's a GUI environment, if you can close the document or whatever triggered the blow-up and free the resources, that's probably a better idea.
Drifting topics here...
I'm fortunate that most of the programming I have to do is best served by Perl's "die", "croak" and "carp" functions. Usually, whatever error my scripts encounter is best handled outside the script, because the error is either bad input, or a bug in the code. Neither of those can really be handled within the script itself. So, we pop out an error message and a stack trace and say "here, you fix it."
Before you say "you're putting an undue burden on your users," most of this code is developed for ourselves to use. I work with a chip design team, and we manufacture and eat our own dog food. Just as the scaffolding around a skyscraper-under-construction doesn't need to be ADA compliant ("What, no wheelchair ramp up here?"), our scripts for internal use don't need quite as much polish as something we'd ship as a product. :-)
That said, I do also work on code that I intend other less-technical people to use. It takes considerably more work to make that code bulletproof and friendly. I'd say more work goes into polish than into the core algorithms.