Have you tried moving the files (on the offending machine) to where the excel exe is? I've gone through DLL hell before and usually it's a case of the application not 'finding' the DLL (even when you put the DLL in the system32 folder).
The reason why it would work on the machine that it was compiled on is because when you compile the DLL, somewhere along the line it does some installation stuff for the DLL which allows it to work when you run excel. At least that's what I've found in my experience. I would also suggest that you create a virtual machine that you can test your stuff on and at least then you will have a 'clean machine' where you can play around
Hope that helps