smallcompany - 6:57 pm on Mar 22, 2012 (gmt 0)

How is WMT getting the idea that these pages "should" exist?

Don't know yet. I started looking into raw log files. Google WMT does not help as I can only see the dates when the server started returning 404 for those links. I actually need to see the initial request whenever it happened. The rest was just an effect of broken linking.

How (and where) is the title-of-the-page string being created and appended to the URL?

No idea. This may take another investigative effort like this AcceptPathInfo which BTW has been mentioned here many times. I'll be searching more on this through old WebmasterWorld posts.

Don't use relative linking to images, CSS files or JS files.

This does not matter as such pages do not exist nor they should return 200, at least in this case. These pages have to return 404.

I'm still puzzled with the Apache's explanation of AcceptPathInfo as it does not mention that a server in CGI mode would not accept the directive. Yet, I'm coming across references that folks had to switch their servers configurations to Apache in order to get this work.
In my case, I can't do it as I have quite a few hosting plans that are plain shared plans. There has to be a way for shutting this feature off.

Thanks