How to make Mockito throw an exception when a mock is called with non-defined parameters?

You could provide a default Answer in the construction of your mock that always throws an exception. Then every call that is stubbed will act like usual. Everything outside those paths will throw an exception. Something like this:

final String arg = "some arg";
Collection<Object> object = mock(Collection.class, new Answer<Object>() {
    @Override
    public Object answer(InvocationOnMock invocation) throws Throwable {
        throw new IllegalArgumentException("You cannot invoke " + invocation.getMethod() +
                                    " with " + Arrays.toString(invocation.getArguments()));
    }
});
doReturn(true).when(object).add(arg);

object.add(arg); // Goes ok
object.add("azertyuiop"); // Throws the exception