Real quick, I had a similar problem and after a lot of Googling, hacking, trying, retrying, and a bit of swearing, I figured out the cause in my case.
I had created the website with a section of pages without a parent. Then, we decided to move the entire section under a parent to organize the site better. A couple of weeks after launch, I got ONE report of a user with IE 8 that they couldn't get to any of the pages that had been moved.
Changing the permalinks from custom (/%category%/%postname%/) to Default worked but was undesirable. Eventually, I moved the entire section under "No Parent" again and it solved the problem.
Just thought I would pass this information on as a possible solution for others in the same situation. Good luck, and thanks for the great discussion that helped me solve my problem!