Thanks to Samuel Neves for pointing me in the right direction. I took a look at the reference mentioned, and it touches on how Theorem 6.1 fails for weak security. It also covers a MAC that is weakly secure without verification queries but loses its security in the presence of verification queries.
Why Theorem 6.1 breaks down
I found that the subtlety occurs in how the attack games are defined. The adversary can send any message-tag pair $(m, t)$ for verification so long as it is not among the previously signed pairs. What's important is that in the original definition of security the adversary wins the attack game if and only if the adversary sends a valid, previously unseen message-tag pair for verification. The equivalency follows from the definition of the winning condition.
However, under weak security, the forward direction still holds (sending a valid $(m, t)$ pair where $m$ has never been seen before clearly forms a valid never before seen pair) but the backwards direction fails. The backwards direction could fail because the adversary could obtain a $(M, T)$ pair from a signing query and then submit a valid $(M, \bar{T})$ pair by modifying the tag $T$. $(M, \bar{T})$ is a valid and previously unseen pair, but the adversary fails to win because the pair involves a message that was previously signed.
Where Theorem 6.1 fails for weak security is when the authors assert $\text{Pr}[W_0] = \text{MAC}^\text{vq}\text{adv}[\mathcal{A, I}]$ which assumes winning the attack game is equivalent to presenting a valid, previously unseen message-tag pair. In the above extreme example above, this is not the case as it is possible for $W_0$ to occur but without winning the weak security attack game.
How to solve the exercise
As for how to construct a MAC system that is weakly secure without verification queries but is not weakly secure with verification queries, you basically construct a system where after receiving $(M, T)$ from a signing query an adversary can easily construct valid $(M, \bar{T})$ pairs. By presenting these valid but not-winning pairs, the adversary learns enough information to break the MAC system.
Let $\mathcal{K} = \{0,1\}^\ell$ and $|\mathcal{T}|$ be super-poly. Let $F$ be a PRF defined over $(\mathcal{K, M, T})$, $k \stackrel{R}{\gets} \mathcal{K}$ and $\mathcal{I} = (S, V)$ be a MAC defined over $(\mathcal{K, M, T} \times \{\perp, 0,\ldots,\ell-1\})$. The signing algorithm is defined to be $S(m) = (F(k, m), \perp)$ and the verification algorithm is
V(m, (t, i))
// Validate tag against PRF
d = F(k, m) == t
if !d or i == ⟂
return d ? accept : reject
// Return ith bit of the key
return k[i] == 1 ? accept : reject
The correctness property hold because the second component of $S(m)$ is $\perp$ which enters the if statement. This MAC system essentially is the deterministic MAC system derived from $F$ but with an extra index field.
First we notice that $\mathcal{I}$ is weakly secure without validation queries. If an adversary wins, then the adversary submitted a valid pair $(m, (t, i))$ where $m$ was not seen before. This means $\textsf{accept}$ was returned which implies $d$ is true in $V(m, (t, i)))$ (either the if statement was entered where $\textsf{accept}$ was returned or the if statement did not execute which implies $d$ was not false). This happens with negligible probability by Theorem 6.2 as $d$ being true means a forgery was made against the deterministic MAC derived from $F$ (this MAC is secure under the stronger definition of security).
However, $\mathcal{I}$ is not weakly secure with verification queries. An adversary that breaks the security is
Let m be an arbitrary message
Obtain (m, (t, ⟂)) from the challenger
k[0..l-1] = 0
for i = 0 .. l-1
Let r be the challenger's response to the validation query (m, (t, i))
if r == accept
k[i] = 1
else
k[i] = 0
// The key has been reconstructed
Let m' be an arbitrary message not equal to m
// Compute the tag of m' with the reconstructed key
Let t' = S(m')
Send the validation query (m', (t', ⟂)) to the challenger
