MinGW Runtime ソースやら Makefile やらを眺めて色々やったところ、
一応「-nostdlib」を指定した際の警告ととエラーは消え、無事にできたようです。ようなのですが、少し不安です……。
下にソースとコンパイルオプションを書きますが、
C ではなく C++ でコンパイルする（拡張子を .cpp にするか g++ を使う）と警告が出ます。
どちらでも一応動くようですし、ダンプしたら無駄がなくなっていた（と思う）のですが、問題はないでしょうか。

// main.c
#include <windows.h>
void WinMainCRTStartup()
{
MessageBox( NULL, "WinMainCRTStartup()", "Info", MB_OK);
ExitProcess(0);
}

// gcc -o main.exe main.c -mwindows -nostdlib -s -Wall -lkernel32 -luser32

// g++ -o main.exe main.c -mwindows -nostdlib -s -Wall -lkernel32 -luser32
C:\Program_Files\MinGW\bin\..\lib\gcc\mingw32\3.4.2\..\..\..\..\mingw32\bin\ld.e
xe: warning: cannot find entry symbol _WinMainCRTStartup; defaulting to 00401000