As an extension of Daniel's answer, let me provide an explicit construction of a non-PRF MAC scheme like he describes.
I will start by assuming that $\Pi = (Gen, Mac, Vrfy)$ is a secure deterministic MAC scheme (which may or may not be a PRF), and I'll use it to construct a second MAC scheme $\Pi' = (Gen', Mac', Vrfy')$ which is also a secure MAC (in the sense that any attacker who can break $\Pi'$ can also break the original scheme $\Pi$) but which is explicitly not a PRF.
Specifically, let $[a,b]$ denote some unambiguously decodable encoding of the pair of strings $a$ and $b$, and let:
- $Gen' = Gen$,
- $Mac'_k(m) = [Mac_k(m), m]$, and
- $Vrfy'_k(m, \tau') = \textsf{true}$ if and only if:
- $\tau' = [\tau, m]$ for some string $\tau$, and
- $Vrfy_k(m, \tau) = \textsf{true}$.
That is, the tags generated by $Mac'$ include a copy of the full input message, and $Vrfy'$ includes an extra check that this copy indeed matches the message the tag is being verified against.
Clearly, $\Pi'$ is a valid MAC scheme, in the sense that $Vrfy'_k(m, Mac'_k(m)) = \textsf{true}$ for any $k \leftarrow Gen'$. Also, by construction, given oracle access to $Mac_k$ and $Vrfy_k$ instantiated with a random key $k \leftarrow Gen$, we can easily simulate $Mac'_k$ and $Vrfy'_k$. Thus, given any adversary $A'$ against the modified scheme $\Pi'$, we can trivially convert it into an equally effective adversary $A$ against the original scheme $\Pi$ by replacing all calls to $Mac'_k$ and $Vrfy'_k$ with their simulated equivalents, and removing the redundant copy of the message from the tag in the final forged output.
If the adversary $A'$ would succeed in forging a message against $\Pi'$ with a non-negligible advantage, then so $A$ would have (at least) the same advantage against $\Pi$. Conversely, this implies that if no such adversary exists against $\Pi$, then none can exist against $\Pi'$ either, and so that the modified scheme $\Pi'$ is (at least) as secure (as a MAC) as the original scheme $\Pi$.
(The subtle part here is that, by the definition of the MAC security game, $A$ fails if it outputs a pair $(m, \tau)$ after having previously received the tag $\tau$ by querying $Mac_k(m)$. But it's easy enough to show that, for this to happen with our constructed adversary $A$, the simulated adversary $A'$ would have had to output $(m, [\tau, m'])$ for some $m'$ in the same situation. If $m' \ne m$, then $A'$ would've failed anyway; otherwise, $A'$ would've previously received $[\tau, m]$ as a response to its simulated query for $Mac'_k(m)$, and so would've also failed.)
On the other hand, $(Gen', Mac')$ is obviously not a PRF over any codomain, at least as long as the message space includes more than one possible message. In particular, let $m_1$ and $m_2$ be two distinct valid messages. Then $Mac'_k(m_1) = [\tau_1, m_1]$ and $Mac'_k(m_2) = [\tau_2, m_2]$ for some arbitrary tags $\tau_1$ and $\tau_2$, whereas, for a random function $f$ with the same domain and codomain, it is (by definition) equally likely that $f(m_1) = [\tau_2, m_2]$ and $f(m_2) = [\tau_1, m_1]$.
This lets us trivially construct a distinguisher: just pick a random input message $m$, query for the corresponding output $f(m)$, and output $\textsf{true}$ if $f(m) = [\tau, m]$ for some tag $\tau$ and $\textsf{false}$ otherwise. This distinguisher will thus always output $\textsf{true}$ if $f = Mac'_k$ for some $k \leftarrow Gen'$, but has at least a 50% chance of outputting $\textsf{false}$ if $f$ is a random function with the same (or larger) codomain as $Mac'$.
