We use a convention to always store files with a date as the beginning
of the filename such as:
2006.12.24_filename.xls or 2006.12.24_filename.xls

How can I get Windows to automatically insert the date in the "Save
as" dialogue and let me fill in the rest?

Macros in templates will not help as we are often using files from
different sources which are not based on my templates.
Installing 3rd party software is not desired but I will consider such
information as an answer.