What is the definition of "security beyond the birthday paradox"? I'm reading a paper about MACs and I would like to be sure about the meaning of a security beyond the birthday paradox.

Is there a definition?
For a MAC algorithm considered to be good, the best way to attack a MAC should be by collision (a birthday attack)

This means, that for MACs with $n$ bit tags an adversary will suceed with a forgery after having issued $q=O(2^{n/2})$ tag queries.

In the literature this bound is called the birthday barrier. 

Now, if you are able to come up with a MAC construction for which you can prove that an adversary will require more queries, say $q=O(2^{2n/3})$ or $q=O(2^{5n/6})$ as for instance shown here, as given by the birthday bound, your MAC provides security beyond the birthday paradox.