The mere thought of multi-threading in C was scary enough... the realization that it will be the best approach for implementing the Winboard interface was very depressing. After some careful reading from various sites, I was pleasantly surprised. It it not hard after all (actually I find it as easy as Java's multi-threading!). Refer to the excellent tutorial by Adrian Worley.
It basically boils down to passing a function (Java eat your heart out!) to another function, which will then execute the function as a thread. Other elements such as critical sections, waiting for threads and juggling information between threads are straight forward and provided by the Windows API. The only drawback of this approach is the fact that my current implementation will not be platform independent (i.e. between Unix and Windows) as the Java implementation is (...here C will eat its heart out :)).
I have implemented crude move ordering, but I am not yet satisfied with speed increase I gained. I also got Arena to work for testing, once my WinBoard protocol (UCI later) is up and running.