Finding a tag that introduced a submodule change

I have a repository with a single submodule in it. Since the parent repository represents the code base for an actual product, I tag release versions in the parent repository. I do not put tags in the submodule since multiple other products may be using it there and I wanted to avoid ambiguous tags.

Sometimes I run into a situation where I need to find out which release of the product a submodule change was introduced in. This is nontrivial, since there are no tags in the submodule itself. This is one thing I tried:

1. Do a `git log` in the submodule to find the SHA1 representing the
change I want to check for
2. In the parent repository, do a git log with pickaxe to determine
when the submodule itself changed to the value of that SHA1.
3. Based on the result of #2, do a `git tag --contains` to see the
lowest-version tag that contains the SHA1, which will identify the
first release that introduced that change

However, I was not able to get past #2 because apparently there are cases where when we move the submodule "forward", we skip over commits, so the value of the submodule itself never was set to that SHA1.

I'm at a loss here on how to easily do this. Can someone recommend a way to do this? Obviously the easier the better, as I have to somehow train my team how to do this on their own.

Thanks in advance.