Уря! Как всегда - нашел решение сам =D
http://article.gmane.org/gmane.comp.gnu.octave.maintainers/9640
Надо было добавить еще ключик -lwldap32
В итоге:
gcc -DCURL_STATICLIB -I ..\..\include simple.c ..\..\lib\libcurl.a -lws2_32 -lwinmm -lwldap32 -o simple
Создает прогу размером 260 Кб, которая не нуждается в libcurl.dll