I initially had permalinks working great with the /archives/%post_id% prefix. Then I added an "archives,php" template to the theme, and created an "archives" "page" based on that template. At some point I noticed weirdness, and so I eventually deleted the page and the template from my directory. I found that now my permalinks were all screwy. After deleting the tamplate and page they would only give the old "no posts matched your criteria" error. I deleted my .htaccess file, cleared my cache, and all that. Same problem. I had someone else at at another computer (in another location entirely) try and they got the same error. They had never been to my page so it wasn't cache or cookie problems.
I eventually found that permalinks will work if I change them to anything else except /archives/%post_id%
I'm totally baffled. It seems that something got screwed up by having either the template or page called "archives" but they're all gone now and I've totally started witha new .htaccess file.