Import Attachments – not attaching to post_parent

I think that importing attachments separately (which is not possible with native export) is precisely cause for your issue. Importer plugin has following code:

if ( $post_parent ) { 
    // if we already know the parent, map it to the new local ID
    if ( isset( $this->processed_posts[$post_parent] ) ) {    
        $post_parent = $this->processed_posts[$post_parent];
    // otherwise record the parent for later
    } else {
        $this->post_orphans[intval($post['post_id'])] = $post_parent;
        $post_parent = 0;
    }
}

There is some more processing with orphans, but in a nutshell it seems that only posts in same import are being considered for parent. Which kind of make sense, since IDs at the time of export are not guaranteed to be precisely same as IDs at the time of import.