Excel can't load XLL on fresh OS

When I tried to use my XLL for Excel on just installed OS, I run into a problem. Excel was not able to load my XLL. It was able to add XLL to the Add-In list, but it didn't load it silently. And if I restart Excel I get the following error message:

The file you are trying to open, 'GENERIC.xll', is in a different format than specified by the file extension. Verify that the file is not corrupted and is from a trusted source before opening the file. Do you want to open the file now?

The problem was in that my XLL has a dependency on msvcr100.dll. And on clean OS there was no such dll in the folder "c:\windows\system32". So I just copied this dll from another OS and now everything works fine.
So now if I will get such an error again - the first thing to do will be to check dependencies using depends.exe tool.

P.S.: My first thoughts about this problem were that the reason is that I'm using Excel 64 bit or Windows 2008 R2 64 bit, so I was searching for a solution in a wrong direction. I have spent a lot of time just because the shitty code of excel doesn't show any details about the error. I really hate excel.