What are the companies that provide this service (reproducing builds)? I haven't heard of this, but sounds interesting.

Depending on how much effort you're willing to put in, even if you use C++ and Windows, you can still write a program to parse the executable and zero out timestamps and other non-deterministic data. That is actually being done in a BitCoin-related program for Windows I believe.

How do you generate and verify the VirtualBox? If you send the image over to the test lab, then the obvious thing to do is for someone to attack your VirtualBox, and you have the same problem all over again, just at a different level.