Hm. I think perhaps a better way of putting it is that the hard AND issue is when people search using a natural language type query (I know about stop words, assume these are always filtered out) and include some extraneous term, so 'What is that new crime novel by John Grisham about a Penguin I think?' will return nothing, and no amount of extra terms added at the end will help, until you delete 'Penguin'... Of course it's anecdotal, but I still suspect it's one of the reasons for the hard AND to OR switch...
I don't find your examples compelling.
If you want to do an additional search that does not depend on your first terms, you simply bring up a new search window.
In your 'real world' example, the equivalent search queries would go something like
search: new crime novel
result: way way too much stuff
search: new crime novel john grisham pelican
result: exactly the right book because every one of those terms applies