With the help of this great MSDN article, my first idea was to simply check if the process is using an elevated Administrator group, and using AdjustTokenGroups() I would set the Administrator group to SE_GROUP_USE_FOR_DENY_ONLY. Unfortunately though, we can't modify the administrator group on the currently running process as it also has the SE_GROUP_MANDATORY attribute, which makes it inelligable for changing.
The MSDN document has this to say about it:
The AdjustTokenGroups function cannot disable groups with the SE_GROUP_MANDATORY attribute in the TOKEN_GROUPS structure. Use CreateRestrictedToken instead.
So, I am done the following code to achieve this;
bool _IsNewProcessLaunched()
{
    HANDLE hToken = NULL;   
    bool hasRestarted = false;
    if (!OpenProcessToken( GetCurrentProcess(), 
        TOKEN_ASSIGN_PRIMARY | TOKEN_QUERY | TOKEN_DUPLICATE | TOKEN_ADJUST_GROUPS, 
        &hToken )) 
    {
        return hasRestarted;
    }
    PSECURITY_DESCRIPTOR pSID = NULL;
    SID_IDENTIFIER_AUTHORITY SIDAuth = SECURITY_NT_AUTHORITY;
    if(! AllocateAndInitializeSid( &SIDAuth, 2,
        SECURITY_BUILTIN_DOMAIN_RID,
        DOMAIN_ALIAS_RID_ADMINS,
        0, 0, 0, 0, 0, 0,
        &pSID) ) 
    {
        CloseHandle(hToken);
        hToken = NULL;
        return hasRestarted;
    }
    BOOL isAdmin = FALSE;
    BOOL ok = CheckTokenMembership(NULL, pSID, &isAdmin);
    // Create the SID structure for the administrator SID
    SID_AND_ATTRIBUTES adminSID = {0};
    adminSID.Sid = pSID;
    // Create a restricted token which denies the administrator group
    HANDLE restrictedToken;
    CreateRestrictedToken(hToken,RESTR,DISABLE_MAX_PRIVILEGE,&adminSID,NULL,NULL,NULL,NULL,&restrictedToken);
    //Create startup info
    STARTUPINFO si = {0};
    PROCESS_INFORMATION pi = {0};
    si.lpDesktop = L"winsta0\\default";
    si.cb = sizeof( si );
    // Get the current executables name
    TCHAR exePath[MAX_PATH];
    GetModuleFileName(NULL,exePath,MAX_PATH);
    // Start the new (non-administrator elevated) restricted process
    if( CreateProcessAsUser(restrictedToken,exePath,NULL,NULL,NULL,TRUE,NORMAL_PRIORITY_CLASS,NULL,NULL,&si,&pi) == 0)
        hasRestarted = false;
    else
        hasRestarted  = true;
    return hasRestarted;
}
But new process is still running as administrator rather than as the normal user.
How do I accomplish that?