I think I have a quick and dirty solution. The trick is to examine the controls within the page header (for example in the PreRender phase), find the links pointing to CSS-files under the App_Themes folder and make them dynamic (by adding some random information to the query-string). This will most likely tell the browser to invalidate the cached version of the file.
The code:
protected void Page_PreRender(object sender, EventArgs e)
{
    HtmlLink link = null;
    foreach (Control c in Header.Controls)
    {
        if (c is HtmlLink)
        {
            link = c as HtmlLink;
            if (link.Href.IndexOf("App_Themes/", StringComparison.InvariantCultureIgnoreCase) >= 0 &&
                link.Href.EndsWith(".css", StringComparison.InvariantCultureIgnoreCase))
            {
                link.Href += string.Format("?t={0}", DateTime.Now.Ticks.ToString());
            }
        }
    }
}
The output:
    <link href="App_Themes/MyTheme/MyTheme.css?t=634310637798128189" 
        type="text/css" rel="stylesheet" />
Note that you need to have a <head runat="server"> declared in your page's markup in order to be able to access the Header property (otherwise it will be null).