In the applied cryptography book by Boneh and Shoup, Chapter 6 on MACs, it is stated that one can modify SUF-CMA game by removing verify oracle access to the adversary. Therefore, the two versions are equivalent(within some factor in the advantage).
However, I am a bit confused by this no-verify version of the game. I have already had some explanation on this but I am still lost... Informally it seems to me that since the verification algorithm doesn't appear anywhere in the game, nothing prevents me from defining a MAC that does some kind of verification (i.e conditions to accept or reject) but also behaves insecurely. For instance, the verification algorithm also broadcasts the MAC key.
My first (failed) attempt was, starting with a secure MAC $M$, create a new one $M'$ such that one of the tag values ($\tau$) will never be used. And modify the new verification algorithm to reject any $(m,\tau)$ and output the key on such input. However, this construction doesn't meet the correctness requirement, i.e the output is not a bit. Therefore this counter-example would not be valid
So my questions are as follows:
Is it really OK, that the game doesn't use all of the algorithms and will remain secure as long as it is correct?
What is wrong with my failed counter-example? Namely, is it or not possible to find a correct counter-example such that the verification algorithm behaves insecurely?