>Given this scheme, how would you distribute a security patch? Is each user of the library supposed to re-compile against the patched library?

No, this is the responsibility of the server which distributes binaries to users via the package manager.