The obvious first step would be to ensure that the service stops properly before being deleted on uninstall. This behavior could be different on different boxes (but it sounds like you test on the same box). See this thread: http://forum.installsite.net/index.php?showtopic=16458
Next, try some diffing on the MSI files themselves and the folders they deliver / install to verify what could be different (if anything).
Try to use dark.exe from the Wix toolkit on the two different MSI files. This will decode them to Wix XML, then use a compare tool such as Beyond Compare, or a similar disk-diff tool, to determine if there are any significant differences between them.
Beyond Compare from http://www.scootersoftware.com/ - is hands down a brilliant tool (no affiliation obviously). I use it all the time, and its usefulness is immediate and a tool all professionals working with files would benefit from every day. Try it. See a screenshot.
Also run a file diff on the installed folders to see if there are any obvious differences. Pay special attention to config files and do a full binary level difference (not just CRC / hashes).
Export your registry hives from HKCU and HKLM (just for your application, not the whole registry) and compare them in before and after states too (4 exports).
As to the differences seen between machines - it sounds like you are using a test virtual, but I just want to add that the presence of visual studio on your box could affect things even if everything else is the same. Other than that the hardware, network and firewall configuration sound like they are the same and that you are testing on a test box.
Have you tried using dependency walker? I have never used it for services, but the profiling option is useful for checking applications in general (how-to).