Refactor out method missing logic into single function

Also makes sure we store the original name as a seen name, so we
invalidate the cache when needed on these names.