Hi Ben,
Thanks so much for investigating! Showing deleted content in search is not by design and there's definitely a bug here. I'll investigate on my end see if I can narrow down the problem.
Do you see other deleted pages in results as well or is it just this one?
Meanwhile, can you see if deleting the following directories and restarting OneNote fixes the problem (search will be slow for a while after you delete these directories).
/Users/<Your username>/Library/Containers/com.microsoft.onenote.mac/Data/Library/Application Support/Microsoft User Data/OneNote/15.0/MasterIndex/
/Users/<Your username>/Library/Containers/com.microsoft.onenote.mac/Data/Library/Application Support/Microsoft User Data/OneNote/15.0/FullTextSearchIndex/
/Users/<Your username>/Library/Containers/com.microsoft.onenote.mac/Data/Library/Application Support/Microsoft User Data/OneNote/15.0/AccessibilityCheckerIndex/
Thanks!
Abhinav