Security of message authentication codes and tag size
Theoretically, that is correct. Given your approach, the attacker needs to try $2^t/2$ tags on average, while to find the key, he needs to try $2^n/2$ keys on average. In CBC-MAC with AES-256, we have $t=128$. Therefore, the adversary needs to try about $2^{128}/2=2^{127}$ tags to find the correct one. While in this case the brute force needs much less effort than trying to break the key itself (which amounts to $2^{255}$ trial-and-errors), it is still far beyond the  current computing power of supercomputers.

It is worth noting that, we usually take any scheme whose best attack needs at least $2^{80}$ operations as secure. (I read this somewhere, but forgot the reference. Sorry!)