Samizdata - 10:45 pm on Jan 20, 2012 (gmt 0)
I'm a little confused by your description but I will try to help.
What you are reporting is from your error log and seems to be correct if:
* You don't have a file named index.php
* You don't have a file named 406.shtml
If both of the above are true then your access log should show a 404 status for the requests, and seeing "File does not exist" in your error log is perfectly normal.
The question then becomes "who is making the requests, and why?".
In the first case (176.31.104.nn) the request appears to come from a French server farm - it is extremely unlikely to be a human visitor, just another unwanted robot (which may be why mod_security is involved).
The second case is more problematic as it appears to be a mobile device from England that is clicking a Google search result - but they would still see your 404 Not Found page, where you presumably have a link to useful content (your access log will show if they used it).
As far as I can see you are not getting a "406 error" at all.
Whether you ask your host, here or on Devshed, the devil is in the detail.
Hope this helps.