> Changing behavior of such base methods is dangerous 
> and can break existing code.

I agree.  The time to argue an API design is before it released not years later after people have written code that relies on the behavior.  

> To me, semantically, the whole idea of finding nothing, 
> whether in something or in nothing is complete and utter nonsense. 

It might not be something you don't agree with, but it isn't nonsense.  There are a number of ways to view it sensibly (empty sets always a subset of other sets).  There a reason that any() and all() are well-defined for empty iterables.  There a reason that math.factorial(0) returns 1.  Those are useful corner cases that save us from writing special case code.

> Empty string search: I think it is completely valid to be able to find an empty string inside another string,

I concur.

I am closing this one as "not a bug".

Primum non nocere.  First Do No Harm".  Don't break existing code because the OP would "prefer that any attempt to find nothing would result in an exception being raised".  That is a terrible reason to break code.  For better or worse, this state of affairs has existed for a long time and no harm seems to have arisen.

Also keep in mind that the current behaviors are tested, meaning that it is not accidental and is guaranteed across implementations.  See Lib/test/string_tests.py.

Though this is closed as not a bug, feel free to add an example or a mention in the documentation.  Keep it short though.  The purpose of the docs for str.count and str.index are to teach how to use the common case rather than getting lost in a discussion of corner case behavior.  Also, the docs should be affirmatively worded (here is how something works and how to use it) rather than negatively worded (omg, finding nothing is something is nonsense).