A family of Microsoft products that enable users to capture, organize, and reuse notes electronically.
I had what I believe to be the same problem: Notebooks that were deleted still appear as available options to open when selecting "More Notebooks". Attempts to open them result in an error message that the Notebook has either been deleted, not fully synced, or that you do not have permission to access it.
Here is the solution that I found, which is to basically recreate the file that the shortcut is pointing to, then re-delete the shortcut and target.
Open OneNote for Windows 10.
Step 1: Click on "More Notebooks..." then note the exact name of the problematic notebook. Then click "Cancel".
Step 2: Click on the "Notebooks" header at the top left, then at the bottom of the page click on "+ Add notebook".
Step 3: Under the "New Notebook" dialogue box that appears, Enter the exact name of the problematic notebook noted in step 1. You will then find yourself in the notebook that you just created.
Step 4: Right-click on the notebook name at the top left, then select "Close this notebook".
Step 5: Close OneNote for Windows 10.
Step 6: Log into https://www.office.com/
Step 7: From the bar on the left side of the Webpage, open OneNote.
Step 8: You should then see a list of "My Notebooks", that now includes the name of the problematic notebook. On the right-hand side of the page, click on "Manage and Delete".
Step 9: From under My files open the Documents directory, then look for the Notebook(s) that you want to delete.
Step 10: Remove the items from the recycle bin as well.
Step 11: Open OneNote for Windows 10 to check if the items are gone.
I hope this helps.