Two points that I haven't seen highlighted enough in the rest of the discussion.
The only (apparent) purpose of the userids in the permalinks is awarding Announcer badges. Badges and reputation may be fun, but they are just a game and they are not that important. If this is the only reason in favor of uids in permalinks, I think that the cons highlighted by @DmitriPavlov in the question (there is a plausible use case in which they can reveal a referee's identity) outweigh the pros. If they are used internally for other "surveillance" purposes (which I find unlikely), this tilts the scale even more in the same direction.
It is not necessary to make the sharer identity public in order to award these badges. The problem can be easily addressed with some crypto. Just take the userid, salt it, encrypt it with a symmetric key, and throw the result in the permalink. Or, alternatively, use the same method as URL shorteners such as bit.ly: every new click on "share" creates a new entry in a database containing
(random_URL_string, target_question, sharer_uid); Stack Exchange will keep this database private, so they know who created each permalink, but the public doesn't.
Considering these two facts, I see no reason to keep uids in share links.