Невозможно предотвратить несколько экземпляров одной и той же программы от разных пользователей

Вы не показали фактическое значение PREDEFINED_UNIQUE_ID, но я предполагаю, что он создает мьютекс не в Global пространство имен ядра, а вместо этого в пространствах имен для каждого сеанса. Использование пространства имен Global требуется для охвата пользовательских сеансов:

The separate client session namespaces enable multiple clients to run the same applications without interfering with each other. For processes started under a client session, the system uses the session namespace by default. However, these processes can use the global namespace by prepending the "Global\" prefix to the object name. For example, the following code calls CreateEvent and creates an event object named CSAPP in the global namespace:

CreateEvent( NULL, FALSE, FALSE, "Global\\CSAPP" );

...

Another use of the global namespace is for applications that use named objects to detect that there is already an instance of the application running in the system across all sessions. This named object must be created or opened in the global namespace instead of the per-session namespace. The more common case of running the application once per session is supported by default because the named object is created in a per session namespace.

Обновлено: вам также необходимо обработать случай, когда CreateMutex() не может получить доступ к мьютексу в другом сеансе из-за разрешений безопасности. Вам нужно обработать случай, когда GetLastError() возвращает ERROR_ACCESS_DENIED, что само по себе означает, что мьютекс существует.

Попробуйте еще что-нибудь вроде этого:

#define PREDEFINED_UNIQUE_ID _T("Global\\MyUniqueMutexName");

m_hMutex = ::CreateMutex(NULL, FALSE, PREDEFINED_UNIQUE_ID);
// or: m_hMutex = ::CreateMutexEx(&sa, PREDEFINED_UNIQUE_ID, 0, SYNCHRONIZE);
DWORD dwErrorCode = ::GetLastError();

if ((m_hMutex) && (dwErrorCode == ERROR_ALREADY_EXISTS))
{
    ::CloseHandle(m_hMutex);

    //in case the previous instance of APP is still in the process of closing
    ::Sleep(5*1000);
    // consider using WaitForSingleObject() instead, in case the app takes less than 5 seconds to close...

    m_hMutex = ::CreateMutex(NULL, FALSE, PREDEFINED_UNIQUE_ID);
    // or: m_hMutex = ::CreateMutexEx(&sa, PREDEFINED_UNIQUE_ID, 0, SYNCHRONIZE);
    dwErrorCode = ::GetLastError();
}

if (dwErrorCode != 0)
{
    EndSplashWindow();

    switch (dwErrorCode)
    {
        case ERROR_ALREADY_EXISTS:
        case ERROR_ACCESS_DENIED:
            AfxMessageBox( _T("An instance of APP is already running."), MB_OK | MB_ICONERROR | MB_SYSTEMMODAL );
            break;

        default:
            AfxMessageBox( _T("Error checking if an instance of APP is already running."), MB_OK | MB_ICONERROR | MB_SYSTEMMODAL );
            break;
    }

    return FALSE;
}

// OK to run now!
return TRUE;

Или, чтобы свести к минимуму вероятность того, что ERROR_ACCESS_DENIED будет сообщено, вы можете предоставить NULL DACL для CreateMutex():

PSECURITY_DESCRIPTOR pSD = (PSECURITY_DESCRIPTOR) LocalAlloc(LPTR, SECURITY_DESCRIPTOR_MIN_LENGTH); 
if (!pSD) 
{ 
    EndSplashWindow();
    AfxMessageBox( _T("Error allocating security descriptor."), MB_OK | MB_ICONERROR | MB_SYSTEMMODAL );
    return FALSE;
}

if (!InitializeSecurityDescriptor(pSD, SECURITY_DESCRIPTOR_REVISION)) 
{ 
    LocalFree(pSD); 
    EndSplashWindow();
    AfxMessageBox( _T("Error initializing security descriptor."), MB_OK | MB_ICONERROR | MB_SYSTEMMODAL );
    return FALSE;
}

if (!SetSecurityDescriptorDacl(pSD, TRUE, NULL, FALSE))
{ 
    LocalFree(pSD); 
    EndSplashWindow();
    AfxMessageBox( _T("Error setting access for security descriptor."), MB_OK | MB_ICONERROR | MB_SYSTEMMODAL );
    return FALSE;
}

SECURITY_ATTRIBUTES sa = {};
sa.nLength = sizeof(sa);
sa.lpSecurityDescriptor = pSD;
sa.bInheritHandle = FALSE;

m_hMutex = ::CreateMutex(&sa, FALSE, PREDEFINED_UNIQUE_ID);
...

LocalFree(pSD);