Your problem is the supplied library from Developer Files is in 32-bit format and your using 64-bit Strawberry Perl; and thus, 64-bit gcc. Your test program above compiles fine for me with Strawberry 5.18 32-bit:

gcc .\test.c -I.\include -L.\lib -lintl -o test.exe
[download]

Try a 32-bit Perl (and thus 32-bit gcc) or try the following.

Using your existing 64-bit Strawberry (and thus 64-bit gcc), from a cmd.exe prompt in the directory where you unzip both the Developer files (from above) link and the Binaries

pexports .\bin\libintl3.dll > intl.def
dlltool --as-flags=--64 -m i386:x86-64 -k --output-lib libintl.a --inp
+ut-def intl.def
gcc .\test.c -I .\include -L . -lintl -o test.exe
[download]

The above worked for me - creating my own 64-bit libintl.a from the provided libintl3.dll and then compiling test.exe linking that created libintl.a