Is there any reason, other than possible collisions where two pubkeys share the same leading characters, that relays should not support responses for partial pubkey inquiries?

No reason. It's basically the same thing as event lookups.

@fiatjaf would know.. he was pushing for its removal from strfry.. i assume its harder to code.