Over the past 2 days I've made some major progress in compiling libicu on mingw. ICU doesn't officially support mingw, but I was able to find a patch at openttd.org and modify it for our needs. Currently it compiles and gnustep-base is able to link against it. Most of the testsuite tests pass, but a few crash and others fail. This, however, is true about a lot of the tests, not just the ones that need libicu.
In any case, if you're going try it out, and I recommend you do (very exciting stuff), you'll need the attached patch and configure will need these directives: "--prefix=/mingw --libdir=/mingw/bin --disable-strict".