Are you multithreaded?
I've seen issues with opening files with ShellExecute. Not executables, but files associated an application - usually MS Office. Applications that used DDE to open their files did some of broadcast of a message to all threads in all (well, I don't know if it was all...) programs. Since I wasn't pumping messages in worker threads in my application I'd hang the shell (and the opening of the file) for some time. It eventually timed out waiting for me to process the message and the application would launch and open the file.
I recall using PeekMessage in a loop to just remove messages in the queue for that worker thread. I always assumed there was a way to avoid this in another way, maybe create the thread differently as to never be the target of messages?
Update
It must have not just been any thread that was doing this but one servicing a window. Raymond (link 1) knows all (link 2). I bet either CoInitialize (single threaded apartment) or something in MFC created a hidden window for the thread.