If you use fiddler2 (http://www.fiddler2.com/fiddler2/) you can see exactly what headers are getting sent to IE which may help you in debugging.
Perhaps you can post the resulting headers here?
I doubt that adding the Content-Type and Content-Disposition prior to the redirect will have any affect, since the browser sees the redirect header and makes a completely new http request to the redirected url, which will be an entirely different set of headers.
However, you might try a Server.Transfer which is a server side redirect, something like the following:
Response.Clear(); //In case your .aspx page has already written some html content
Response.AddHeader("Content-Type", "application/octet-stream");
string disp = String.Format("attachment; filename={0}", fileName); // fileName = file.exe
Response.AddHeader("Content-Disposition", disp);
Server.Transfer(@"http://www.example.com/file.exe?id=12345");
Or alternatively, use Response.BinaryWrite :
Response.Clear(); //In case your .aspx page has already written some html content
byte[] exeContent = ... //read the content of the .exe into a byte[]
Response.AddHeader("Content-Type", "application/octet-stream");
string disp = String.Format("attachment; filename={0}", fileName); // fileName = file.exe
Response.AddHeader("Content-Disposition", disp);
Response.BinaryWrite(exeContent);