If you want to try a long shot (basically idiotic) idea, try putting a copy of the dll file in the same folder as the .c file (where you are compiling it).
I think it might need to be there (or in a standard location) for the exe to run anyway.
BTW, are you using MinGW? Is that how you are compiling with gcc on windows?
EDIT: Another possibility, rename the .lib file to .dll.a. Give it a try.