How to create an attachments archive with working pagination?

Allright, here’s how I got it working:

Rewriting the query inside a template file wouldn’t work because the main query already found 0 results based on the wrong assumption that attachments should not be queried. Thus the template file doesn’t even run but jumps to 404.php where everything is too late.

So one has to change the query right after it got parsed and before results were retrieved. WP provides the hook parse_query for this.
See this: http://codex.wordpress.org/Plugin_API/Action_Reference
http://codex.wordpress.org/Query_Overview

add_action('parse_query', 'hijack_query');

function hijack_query() {

    global $wp_query;

    // When inside a custom taxonomy archive include attachments
    if (is_tax('brands') OR is_tax('author')) {
        $wp_query->query_vars['post_type'] =  array( 'attachment' );
        $wp_query->query_vars['post_status'] =  array( null );

        return $wp_query;
    }

}

'brands' and 'author' are custom taxonomy archives showing attachments assigned to those taxonomies. Change the if statement to your needs so the query is only overwritten when necessary. Note that is_tax() returns false on category archives and tag archives: if you registered categories or tags as an attachment taxonomy, use is_category() or is_tag() respectively.