I just spent two days trying to work out this problem:
From the Reading Settings page, I chose to have a static page, and I selected the appropriate page from the Front page drop-down menu. Now, that page is displayed as my index. Good!
However, when someone entered an invalid URL, instead of returning the 404.php page (or even the <?php else : ?> section of the index.php) it returned a page that had every single page publish compiled into one page. Bad!
After mucking around with pretty much everything, I discovered that I must ALSO select a page from the Posts page drop-down menu. Now, any 404 error is successfully redirected to my 404.php page. I guess it fixes a hole in the loop?
I thought this might be a bug because the documentation on this site suggests that you should be able to leave Posts page blank if you want. I would like to, but for now I created an extra (hidden) page just so I can choose it from this menu and make everything good again.