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
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
gcc .\test.c -I .\include -L . -lintl -o test.exe
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