added a comment - - edited
Thanks for bringing this up. After much deliberation, we're leaving the new behavior in 0.10.6. Our old behavior (searching through the command line looking for a valid command) was consistent with Ruby 1.8, but not with the command line (cmd.exe) or with Ruby 1.9. We strive to go with the principle of least surprise, so we're picking the new behavior that is consistent with the command line (and which also happens to be more secure).
The new behavior requires quotes around the program name, so you can modify the recipe like so to make it work (and the quotes are backwards compatible, so you should be able do it even before you upgrade Chef):
execute '"C:\\Program Files\\My Program\\The Program.exe"'
I hope it doesn't cause too much churn for you.