I think the problem stems from the fact that, in my opinion, the official documentation is a bit ambiguous on the meaning of Non-Python created threads. Quoting from it:

When threads are created using the dedicated Python APIs (such as the threading module), a thread state is automatically associated to them and the code showed above is therefore correct. However, when threads are created from C (for example by a third-party library with its own thread management), they don’t hold the GIL, nor is there a thread state structure for them.

I have highlighted in bold the parts that I find off-putting. As I have stated in the OP, I am calling PyThread_start_new_thread. Whilst this creates a new thread from C, this function is not part of a third-party library, but of the dedicated Python (C) APIs. Based on this assumption, I ruled out that I actually needed to use the PyGILState_Ensure/PyGILState_Release paradigm.

As far as I can tell from what I've seen with my experiments, a thread created from C with (just) PyThread_start_new_thread should be considered as a non-Python created thread.

There are two methods of multi threading while executing C/Python API.

1.Execution of different threads with same interpreter - We can execute a Python interpreter and share the same interpreter over the different threads.

The coding will be as follows.

main(){     
//initialize Python
Py_Initialize();
PyRun_SimpleString("from time import time,ctime\n"
    "print 'In Main, Today is',ctime(time())\n");

//to Initialize and acquire the global interpreter lock
PyEval_InitThreads();

//release the lock  
PyThreadState *_save;
_save = PyEval_SaveThread();

// Create threads.
for (int i = 0; i<MAX_THREADS; i++)
{   
    hThreadArray[i] = CreateThread
    //(...
        MyThreadFunction,       // thread function name
    //...)

} // End of main thread creation loop.

// Wait until all threads have terminated.
//...
//Close all thread handles and free memory allocations.
//...

//end python here
//but need to check for GIL here too
PyEval_RestoreThread(_save);
Py_Finalize();
return 0;
}

//the thread function

DWORD WINAPI MyThreadFunction(LPVOID lpParam)
{
//non Pythonic activity
//...

//check for the state of Python GIL
PyGILState_STATE gilState;
gilState = PyGILState_Ensure();
//execute Python here
PyRun_SimpleString("from time import time,ctime\n"
    "print 'In Thread Today is',ctime(time())\n");
//release the GIL           
PyGILState_Release(gilState);   

//other non Pythonic activity
//...
return 0;
}

2. Another method is that, we can execute a Python interpreter in the main thread and, to each thread we can give its own sub interpreter. Thus every thread runs with its own separate , independent versions of all imported modules, including the fundamental modules - builtins, __main__ and sys.

The code is as follows

int main()
{

// Initialize the main interpreter
Py_Initialize();
// Initialize and acquire the global interpreter lock
PyEval_InitThreads();
// Release the lock     
PyThreadState *_save;
_save = PyEval_SaveThread();


// create threads
for (int i = 0; i<MAX_THREADS; i++)
{

    // Create the thread to begin execution on its own.

    hThreadArray[i] = CreateThread
    //(...

        MyThreadFunction,       // thread function name
    //...);   // returns the thread identifier 

} // End of main thread creation loop.

  // Wait until all threads have terminated.
WaitForMultipleObjects(MAX_THREADS, hThreadArray, TRUE, INFINITE);

// Close all thread handles and free memory allocations.
// ...


//end python here
//but need to check for GIL here too
//re capture the lock
PyEval_RestoreThread(_save);
//end python interpreter
Py_Finalize();
return 0;
}

//the thread functions
DWORD WINAPI MyThreadFunction(LPVOID lpParam)
{
// Non Pythonic activity
// ...

//create a new interpreter
PyEval_AcquireLock(); // acquire lock on the GIL
PyThreadState* pThreadState = Py_NewInterpreter();
assert(pThreadState != NULL); // check for failure
PyEval_ReleaseThread(pThreadState); // release the GIL


// switch in current interpreter
PyEval_AcquireThread(pThreadState);

//execute python code
PyRun_SimpleString("from time import time,ctime\n" "print\n"
    "print 'Today is',ctime(time())\n");

// release current interpreter
PyEval_ReleaseThread(pThreadState);

//now to end the interpreter
PyEval_AcquireThread(pThreadState); // lock the GIL
Py_EndInterpreter(pThreadState);
PyEval_ReleaseLock(); // release the GIL

// Other non Pythonic activity
return 0;
}

It is necessary to note that the Global Interpreter Lock still persists and, in spite of giving individual interpreters to each thread, when it comes to python execution, we can still execute only one thread at a time. GIL is UNIQUE to PROCESS, so in spite of providing unique sub interpreter to each thread, we cannot have simultaneous execution of threads

Sources: Executing a Python interpreter in the main thread and, to each thread we can give its own sub interpreter

Multi threading tutorial (msdn)