Welcome to WebmasterWorld Guest from 188.8.131.52
You start out by saying "pages that do not exist" and then you talk about Xenu looking for links.
Did these pages ever exist, even in prototype form, and even if there were no links to them? If they did, there are explanations about how Google might have found them.
Things like xyz.html existing and xyz.html/ returning the same page would be a hint. Or say /things/xyz.html and /things//xyz.html would be another.
You may find that your server configuration may be causing you some headaches.