Does anyone know of a patcher that would pass this simple test?
Yes, NINJA does.
In a typical (?) patching process, offsets are used to identify the location of bytes that will be changed/removed/inserted. An another way to identify the location would be searching for a unique byte sequence that resides in/near it, and then perform the necessary operation.
You could, but that methodology is subject to false positives, and bloated sizes as you need a long identifying byte string to be more reliable. I think most people are more interested in reliable patching.
I think a better approach is a patching format (such as NINJA) that strips away superfluous information such as the header, and reliably applies changes using offsets and operations relative to the common useful area of interest (that results after stripping). This pretty much takes care of all practical cases where you can reliable apply the same patch to different source files. You could make an argument for cases where the bytes are shifted. However data shifting is usually accompanied by an altered loading code to go with the new location. This would render most patches of this nature incompatible unless it were very simple and changed data only. That's probably going to be the minority of cases.