FileExists, FindFirst, CreateFile только проверит на наличие файла, а запустилась программа или нет не поможет.
SHELLEXECUTEINFO ExecuteInfo;
ExecuteInfo.lpFile = part.c_str();
ExecuteInfo.lpParameters = "open";
ExecuteInfo.fMask = SEE_MASK_NOCLOSEPROCESS;
ExecuteInfo.nShow = SW_SHOWNORMAL;
А размер структуры установил? Еще желательно обнулить структуру ZeroMemory.
if (ShellExecuteEx(&ExecuteInfo))
Проверять надо не результат функции а параметр ExecuteInfo.hProcess:
hProcess
Handle to the newly started application. This member is set on return and is always NULL unless fMask is set to SEE_MASK_NOCLOSEPROCESS. Even if fMask is set to SEE_MASK_NOCLOSEPROCESS, hProcess will be NULL if no process was launched. For example, if a document to be launched is a URL and an instance of Microsoft Internet Explorer is already running, it will display the document. No new process is launched, and hProcess will be NULL.
Note ShellExecuteEx does not always return an hProcess, even if a process is launched as the result of the call. For example, an hProcess does not return when you use SEE_MASK_INVOKEIDLIST to invoke IContextMenu.
MSDN.
Проверять можно по таймауту:
if (WaitForSingleObject(ExecuteInfo.hProcess, 500) != WAIT_OBJECT_0)
ShowMessage("Приложение не запускается");
Здесь 500 - таймаут, который ждет программа на запуск приложения.