I took a closer look at Windows Notepad and discovered that while the Find and Replace dialogs do not have system menu icons, they do have system menus accessible by Alt+Space. So these two patches aren't the solution after all.
I came up with a new patch that seems to fix the problem properly and posted it to Bugzilla: http://bugs.winehq.org/show_bug.cgi?id=29336
Please let me know if this new patch is the correct solution.
-Alex