Update 03/11/2016: I have patched the sources to fix the problem mentioned in my original post. I have submitted that patch also to ICU upstream ticket: 12840

The latest ICU 58.1 is compiled with MSVC 2008, 2010, 2012, 2013 and 2015. The precompiled static libraries are linked against the static MSVC runtimes (/MT instead of /MD).
There seems to be a problem building the cintltst test in MSVC 2008, 2010 and 2012, but not with MSVC 2013 and 2015. Chances are this is because of C98 incompatibility, but lets see if its fixed upstream. I am uncertain if that causes any issues with the respective builds right now.

You can fetch it as usual in the Precompiled ICU page. Older builds are now hosted in the Precompiled ICU (Past Builds) page.

Any feedback is welcome. enjoy.