I have Office 2007 and kept running into an annoying problem where Excel attachments and Excel files couldn't be opened from Outlook or even Explorer. I would get the "Windows cannot find" error dialog.
Strangely, the solution was this:
Open the Excel options, go to the advanced tab, under the general heading uncheck the box that says "Ignore other applications that use Dynamic Data Exchange (DDE).
Hope this helps others that may run into this.