My recommendation for this NPC naming issue is similar to a fix I've already suggested to get rid of duplicate local announcements. (You should not see the same wedding barge message more than once in approximately 15 minutes.)
These name and message strings have no effect on gameplay, so some of the smarts can be moved to the local client. Hash the name/message to get a unique integer value. A message hash should include the sender. Locally filter out any duplicate messages. Send the recently killed NPC name hashes to the server, so it can generate a new one.
These name and message strings have no effect on gameplay, so some of the smarts can be moved to the local client. Hash the name/message to get a unique integer value. A message hash should include the sender. Locally filter out any duplicate messages. Send the recently killed NPC name hashes to the server, so it can generate a new one.