Re: Removing unloaded functions from auto-mode-alist.

[Richard Stallman]

    I guess it can't hurt to leave a function on a hook or in
    auto-mode-alist if it is replaced by a restored autoload. (Even if
    feature x actually put it there.)  See patch below.  Erring on the
    other side seems more damaging: removing a function from a hook when
    that function was put there by a user's init file or something.

Usually when a package defines a function and puts it on hooks, that
function will not be autoloaded.  If the function is autoloaded, that
means it is meant to be used when the package is not loaded.  So that
function might be put on hooks by users before the package is loaded.

So I think what you're proposing is the right criterion.
It would be right most of the time.