Vulnerabilities of encrypting data with known regularities
Typically the cost of brute force so greatly out weighs the cost of decrypting a single block, that the fact that an adversary can check for proper decryption after decrypting a single block is not a serious concern. Otherwise protocols like SSL would not be secure.

That said, as you point out, this relates to the key space. If the key space is too small, then decrypting the first block with every possible key would be feasible for an adversary. If you could make it necessary to decrypt every block in order to get the plaintext, that would slow down an adversary. But, with the speeds we see in encryption algorithms, you'd have to encrypt terrabytes for this to matter. For example, the throughput of AES running on a GPU was shown to be around 35,000 Mbps. That number will only continue to rise. The point is to use a cipher that supports a large enough key space and choose keys randomly from the entire space.

If you still feel this is a problem though, why not do the following $E^{ofb}_{k_1}(E^{cbc}_{k_2}(P)||k_2)$ where $||$ is concatenation and $P=p_1\cdots p_n$ (i.e., a number of blocks of plaintext). The use of OFB on the outside ensures that the entire ciphertext must be decrypted to get the last block ($k_2$), which is then used to get $P$.