Comment 8 for bug 589236

Ok, I had a short look at why application/octet-stream is handled that way:

Currently (Firefox 3.0.1) if the mime-type is application/octet-stream (or application/x-msdownload) a simplified download UI is used which only allows a download of the file if there is no default application defined (which is the case on Linux at least for application/octet-stream).

If that simplified wouldn't be used "Open" would still be denied because of:

      // We don't let users open .exe files or random binary data directly
      // from the browser at the moment because of security concerns.

(that's a source code comment and so it seems that this behaviour/regression was intended in the first place)

The overall question is if the HelperAppService is supposed to return a default handler for the recognized file extension if application/octet-stream is used as mime-type?

Anyway there is a quick'n'dirty workaround to get a usable download UI back:
Add for example the following line to your ~/.mailcap:

application/octet-stream;/bin/true "%u"

By doing that the HelperAppService returns a default application (/bin/true) and the above constraints don't apply anymore. So you'll also get back the other alternatives returned by the MIMEInfo.