This answer points out that certain key and block lengths were a requirement for the AES submissions:
The candidate algorithm shall be capable of supporting key-block combinations with sizes of 128-128, 192-128, and 256-128 bits.
My question is this; how can having a key length that is greater than the block size enhance security?
If we look at ECB mode for simplicity, when the key length is equal to the block length we have a permutation relationship between the set of all plaintexts and the set of all ciphertexts.
Once you increase the key length beyond that, you start to introduce collisions. In fact, you only introduce collisions from then on don't you? Collisions in the sense that a key will create the same ciphertext-plantext relationship as another key.
This would lead me to believe that only part of the key-space is unique, and only that part of key-space needs to be brute-forced?
I know that I am clearly incorrect, I just don't understand why.