Immediately after `git init`, do `git commit --allow-empty -m"initial empty commit"`. Now you have an empty commit, and any other repo which has this empty commit has some history in common with your repo.
The SHA-1 hash is well-known and there are plenty of articles you can find about it, if you search for 4b825dc642cb6eb9a060e54bf8d69288fbee4904
Here's one for example:
https://stackoverflow.com/questions/9765453/is-gits-semi-sec...
I'm not sure this helps for projects which have a shared development history, but not a shared commit history. But within an organization, where you have projects which may split and/or merge, it can help to bridge some gaps.
Is the really only reason why people do this, so that you can rewrite your initial working commit in a rebase? I think that might be it. (You can't easily rewrite the initial commit with a rebase.)
This comes at the cost of having intentionally multiple histories and is not well-suited for complicate cases, but for the common case of "we want to stitch this old CVS-history to this commit", it does a good job.
Usability-wise, replace refs are not cloned automatically and some web-based tools lack support for it.