Let me start by saying that I like the idea. Cryptography has always fascinated me. I have even posted a kind of cryptanalysis challenge myself – Cryptographic hash golf (robbers) – and personally would welcome the idea of having more challenges of this kind.
Specifics aside (e.g., breaking a non-trivial steam cipher and performing frequency analysis as parts of the same task might be a bit too much), I think this would make an interesting code challenge if designed as one.
I'm curious whether [...] this would be on topic
In the format you proposed... maybe. Are pure programming puzzles on topic? is still trying to sort this out, and I personally agree with this answer (not the one with the most votes) in that programming puzzles should have an objective winning criterion other than posting time.
Posting time alone means that the contest is really over as soon as somebody posts a working solution, which is unfortunate for several reasons: it gives you no incentive (or possibility, really) to improve on your first working version, there's really no reason to keep working on your partial solution as soon as someone beats you to the punch, and the first answer doesn't even have to be good to finish the contest; the cat is already out of the bag. Granted , cops-and-robbers share these issues, so none of them is a deal breaker.
Having said all of the above, it's difficult to predict if the specific challenge you propose would remain open. The community seems divided on the issue, and it takes only five close voters to put a question on hold.
I'm curious whether [...] there might be any issues with this type of challenge that I haven't thought of, for example does a more powerful computer give too much of an advantage for this type of challenge?
Without having more details regarding the strength of the stream cipher and how much is known about the plaintext, it's hard to tell, but if a successful break is – as you mentioned – possible by reducing the effective strength of the stream cipher, the part that is left might put users with better hardware or deeper pockets at an advantage.
Should it be a requirement that the code used to perform the exhaust be included?
Objective computational challenges without "code" discusses this. The community seems to be leaning towards no, but as you'll be able to tell from my answer, I don't really agree. This site is about programming contests, so – in my personal opinion – answers should contain code.
In this particular case, an answer that contains nothing more than the correct plaintext would close the contest without adding valuable information of any kind to the site. Requiring the actual code that was used mitigates this and has no downsides I can think of.
A different approach
This is just an idea and might result in a better, worse, or simply different challenge type, but I think the underlying concept could make a nice fastest-code challenge.
For example, the challenge could include a few test vectors, and answers would submit solvers that the challenge author or a trusted third party runs with undisclosed ciphertexts. This would mix cryptanalysis (finding vulnerabilities in the stream cipher) with coding (making the exhaustive search quick), without any potential scope issues (that I'm aware of, anyway), without unfair advantages to users with slow computers, and without the one-answer-and-this-is-over situation.