Old git commits can still be seen via references from other repos after the history is rewritten

However, the repository is referenced as a submodule of one of my other repositories.

Note that a superproject—a repository that uses a submodule—refers to the commits in the submodule by raw hash ID.

Clicking the submodule link of the other repository brought me to the old commit

This is to be expected, since the superproject does still refer to the original commit. Since no commit can ever be changed, this superproject commit will refer to the original submodule commit forever.

and can still see all of the old data like before it was rewritten.

That will be the case until the submodule repository drops the original commits.

There are several good questions you can ask here, and you asked one of them:

How can I remove these old rewritten commits?

Before we can answer that, let's look at the first two questions you could have asked:

• Q: Will the submodule repository ever remove those old rewritten commits?

  A: Maybe. Probably. A repository is a database of commits, plus a (usually much smaller) database of names. (A repository in which you do work has some minor additional stuff to make it useful, while a --bare repository as found on a server has very little besides these two databases.)

  Any commit whose hash ID is found directly by a name in the names database is referenced. Such a commit should not, and will not, be deleted.

  Any tag object (one of four internal kinds of Git objects) whose hash ID is found directly by a tag name in the names database is also referenced, and that tag object will then usually link to a commit by hash ID. This commit is also referenced, though indirectly, and should not—and will not—be deleted.

  And, any commit whose hash ID is contained in any referenced commit is itself referenced, indirectly, and should not and will not be deleted.

  The remaining unreferenced commits can be deleted. The Git software will, eventually, delete them. As long as your old commits are unreferenced, they will eventually be deleted. (They probably are unreferenced, but the only way to be sure is to see whether git gc actually deletes them, or write or use a program to check the connectivity here—git fsck can do that for you, for instance.)

• Q: When will Git get around to deleting these commits?

  A: Someday. It's not predictable.

This leads us to a modified version of your own question:

• Q: Is there some way to speed this up?

  A: Yes. If you run the server on which the --bare repository lives, go into the repository in question and run git gc. If not, have someone who does run the server do this. If this isn't a bare repository, or if someone has enabled reflogs, there may be some additional steps to take. Any Git administrator should be aware of these steps, and if not, should consult the list of steps in the git filter-branch documentation.

There's one more question we should note, that you did not ask, but should:

• Q: What happens to the superproject once these submodule commits go away?

  A: It breaks. More specifically, it continues to refer to submodule commits by hash ID, but those commits no longer exist in the submodule repository. To keep the superproject working, we must now rewrite the superproject commits, using a mapping that says, for each old submodule commit hash ID, what the new-and-improved replacement hash ID is.

  If such a mapping is not available, it must be constructed somehow. This is usually painful and difficult, leading people to discard the superproject entirely instead.

  (If the mapping is available—and git filter-branch and other conversion programs should make one available; the original filter-branch did not but this was fixed in the last few years—you'll want a program that understands how to replace gitlink hash IDs. I don't know of such a program, but it must have been written more than once by now.)