I don't agree with your first or third paragraphs but I do kind of agree with the second, yet I think the solution to that is to provide return-value-based solutions where it makes sense, not to avoid exceptions in general.

Also, things like "user canceled this operation" are great for exceptions IMO... exactly how would you stop (say) a sort() function otherwise? You'd need to write a custom cancelable sort, which isn't a great idea? You can't reinvent the wheel for everything.