Indeed. I think your situation could also be handled correctly by my
suggestion:
E.g. we could add to bytecomp.el the ability to force `require' to
reload a package if it's not already loaded from the file that
locate-library returns.
Yes, that's what I'm resorting to now. I'm writing the package so that it reloads itself before doing anything if `locate-library' returns a newer version.
It's a little annoying that it has to visit a file and check every time it's used, but it only happens at byte-compile time, so it's not a huge deal.