alt Hacker NewsWoolly rhinoceroses (related to the Sumatran rhinoceros and a different species from the one from the link in the posting above) have continued to live in Europe and Asia until much more recently, i.e. until around ten thousand years ago (i.e. around the same time when humans were forced to switch from hunting to eating seeds, presumably because of the depletion of the big animals that made hunting profitable).
That is certainly recent enough for their memory to persist in myths.
As you say, the narwhal tooth is indeed the source used for most medieval illustrations of unicorns, but not the source of the legends about them.
That’s more plausible especially when you consider people would find skeletal remains long after the animal went extinct. However, Occam's razor points to African rhinos as a more reasonable source for keeping this myth alive vs thousands of years of oral tradition.
Even just goats seem useful here to explain the often depicted medieval unicorns beards compared to earlier sources.