Bruteforcing a symmetric cipher
You are forgetting that messages usually consist of many blocks and that many messages contain much more structure than just English text. For example an RSA private key will, when encoded, have a easy to distinguish header and will consist of many blocks of plaintext / ciphertext when encrypted with a block cipher. The same is true for Word documents, XML messages, images and many other formats.
Otherwise, it is a simple game of chance. At each block that decrypts correctly according to the available information, you get more confident that you've found the right message. However, you can choose a block for which you have the most information and only continue decrypting the next block once you've found a match. That way you can very quickly filter out wrong keys.
For instance, for English text you'll generally know at least one bit: the highest one bit of ASCII text is always zero, so that already makes 8 bits per block that you need to get right. Assume that you've got another 2 bits per byte / character simply by checking if the English text is consistent after that. Then you only need to advance to the next block once in $2^{8 \cdot 3} = 2^{24} = 16,777,216$. During the calculation of cryptographic strength, we can safely ignore that kind of detail. If the message is very small then such analysis will indeed fail, and you cannot tell if the key is correct or not. This is easy to show by looking at single bit encryption, e.g. using stream cipher mode such as CTR.
As indicated in the comments, generally we also assume that messages have integrity protection and provide message authentication, usually through authenticated cipher modes or explicit inclusion of a Message Authentication Code (MAC) / authentication tag. In that case, the correctness of the key can also be verified through that code. For most modes that add at least 64 bits to test (128 bits for most authenticated modes and 256 or more if HMAC is used).
Usually, for attacks, we assume that (part of) the message is known, i.e. known plaintext for a known-plaintext attack at the very minimum. Ciphers are expected to be even more secure than that: allowing the attacker to choose which messages get encrypted while leaking no information about the data (other then information about the message size). In other words, the ciphertext should be INDistinguishable from random under a Chosen Plaintext Attack, i.e. IND-CPA secure.