How to check if image is already stored in a site’s post database? (network)

Yes, a database query is possible with WordPress:

function is_image_in_network( $image_name )
{
    global $wpdb;
    $image = "uploads/2012/01/{$image_name}";
    $value="%".like_escape( $image ).'%';
    $blog_id = get_current_blog_id();
    $wpdb->set_blog_id( $blog_id );
    $image = $wpdb->get_var( 
        $wpdb->prepare( 
            "SELECT ID FROM {$wpdb->posts} 
            WHERE  post_status="publish" 
            AND post_content LIKE '%s'"
            , $value 
        ) 
    );
    return is_null( $image ) ? false : true;
}

You can use it as function in your templates. Just add the image name, you’re searching for as argument. The new “Template Tag” works like every default WP “Conditional Tag”.

Is that image.php in the Question a typo?

I’m leaving the search string %uploads/2012/01/an_image% without an extension so it can catch all the images (original and thumbnails).

^{Documentation: Class_Reference/wpdb.}