Earlier quoted context omitted.
That's true -- most of these little usability tweaks are harder to do than just slam a message box to the page. But it makes the result much better. Another idea: you can just not delete the notes at all and have some separate "archive" page where you'd keep them all.
I've added an "undo" button - it was much easier than I thought :)
Just tried it. Awesome.
Maybe the fade out after you do undo takes too long. But I love it.