Does the !important rule override media queries?

Media queries and @media rules do not affect the behavior of !important in any way, because they do not have any effect on any part of the cascade. (By extension, this also means you cannot use a @media at-rule to "remove" an !important flag, even if you use a more specific selector.)

When your media query is matched, the browser sees this:

a{
    color:#0000FF!important;
}
a{
    color:#FF0000;
}

And when it doesn't, it sees this:

a{
    color:#0000FF!important;
}

Both cases result in the first ruleset taking precedence, but do not prevent, for example, an !important declaration with a more specific selector, or an !important inline style, from overriding it.

Here's another example which illustrates this better:

a{
    color:#0000FF!important;
}
@media (max-width: 300px){
    a:link,a:visited{
        color:#FF0000!important;
    }
}

When the media query is matched, the browser sees this:

a{
    color:#0000FF!important;
}
a:link,a:visited{
    color:#FF0000!important;
}

This results in the second rule taking precedence because it has a more specific selector (at least for a elements that match either pseudo-class). If it didn't match the media query then only the first rule would have any effect, as above.