Agreed, but Notes should be able to do this anyway - after all, the database knows where the archive is, so it should be feasible to extend the search facility to cater for this.
And not just search! Users should not really need to know or care about archiving. Outlook uses Personal Folders to do much the same as archiving does in Notes, and archiving is used simply to reduce their size. The great thing about that implementation is that they are just in files on the disc (hmm, so they are in Notes) and the interface allows seamless moving of material between on-line, personal folders and archive folders.