It appears that this is a bug in WordPress. I have found the source of the problem and a workaround.

Workaround

If you're not interested in the cause, the workaround is to comment out this bit of cosmetic code in wp-admin/includes/menu.php:

https://github.com/WordPress/WordPress/blob/master/wp-admin/includes/menu.php#L168

/*
 * If there is only one submenu and it is has same destination as the parent,
 * remove the submenu.
 */
if ( ! empty( $submenu[ $data[2] ] ) && 1 == count( $submenu[ $data[2] ] ) ) {
    $subs      = $submenu[ $data[2] ];
    $first_sub = reset( $subs );
    if ( $data[2] == $first_sub[2] ) {
        unset( $submenu[ $data[2] ] );
    }
}

This will mean that some menu items that previously didn't show a submenu now will (with a single item the same as the main menu item), but that is only a cosmetic UI change.

Cause

For those of you that want to know the detail…

Accessing edit.php?post_type=book was failing this check in wp-admin/includes/menu.php:

https://github.com/WordPress/WordPress/blob/master/wp-admin/includes/menu.php#L341

if ( ! user_can_access_admin_page() ) {

    /**
     * Fires when access to an admin page is denied.
     *
     * @since 2.5.0
     */
    do_action( 'admin_page_access_denied' );

    wp_die( __( 'Sorry, you are not allowed to access this page.' ), 403 );
}

The call to user_can_access_admin_page() calls through to get_admin_page_parent().

If the submenu has been removed, get_admin_page_parent() returns an empty parent which ultimately causes user_can_access_admin_page() to erroneously return false in the case of the librarian role (the administrator role passes for a different reason).

If the submenu is left in place, get_admin_page_parent() returns a non-empty parent and the access check proceeds correctly from there.

So the root issue is that the global $submenu is being used to both determine the UI and also to make decisions on the permissions hierarchy. I don't see an immediate quick fix for this problem that wouldn't have side effects elsewhere throughout the WordPress code, other than the workaround above.

I think I've found a workaround for this without having to edit the core files.

As you said, the cause of this bug is that a empty menu that has no sub-menu items will cause access check to erroneously return false.

So the workaround is to not make the list page a top-level menu. Instead, make it a sub-menu under an existing menu. This way there won't be an empty top-level menu and you can see the list page correctly without the 'Add New' button.

This is only a workaround, not ideal. But perhaps it's better than editing the core files.

The way to create a custom post type while putting its list page as a sub-menu item is simple. The args of register_post_type has an arg called show_in_menu. As the docs say:

If a string of an existing top level menu (eg. 'tools.php' or 'edit.php?post_type=page'), the post type will be placed as a sub-menu of that.

So the code will be:

register_post_type('book',
array(
    'labels'                => array(
        'name' => __( 'book' ),
        'singular_name' => __( 'Book' )
    ),
    'capability_type'       => array('book', 'books'),
    'capabilities'          => array(
        'create_posts' => 'do_not_allow'
    ),
    'map_meta_cap'          => true,
    'show_ui'               => true,
    'show_in_menu'          => 'tools.php',   //or whatever top-level menu you'd like
    //... other args omitted
));

I have found 2 Workarounds for this issue:

First off I find it better to assign a specific capability for the custom_post_type create_posts instead of using do_not_allow

So I use:

...
'capability_type'     => 'books',
'capabilities'        => array(
    'create_posts' => 'add_new_books'
),
'map_meta_cap'        => true,
...

This way I can assign Admins or other Managers the add_new_books capability, but don't allow it for other roles.

Option 1:
(Filter the user_has_cap to fake that the user has 'edit_posts' but then remove the Posts Menu Item)

add_filter(
    'user_has_cap',
    function( $all_caps, $caps ) {
        global $typenow, $menu;

        if ( is_admin() && ! empty( $typenow ) && stripos( $_SERVER['REQUEST_URI'], 'edit.php' ) && stripos( $_SERVER['REQUEST_URI'], 'post_type=' . $typenow ) && in_array( 'edit_posts', $caps, true ) ) {
            // Temporarily assign the user the edit_posts capability
            $all_caps['edit_posts'] = true;
            // Now Remove any menu items with edit_posts besides the custom post type pages.
            if ( ! empty( $menu ) ) {
                foreach ( $menu as $menu_key => $menu_item ) {
                    if ( ! empty( $menu_item[1] ) && ( $menu_item[1] === 'edit_posts' || $menu_item[2] === 'edit.php' ) ) {
                        remove_menu_page( $menu_item[2] );
                    }
                }
            }
        }

        return $all_caps;
    },
    10,
    2
);

While this works it does add some PHP Notices for undefined indexes.

Option 2:
(Filter the $pagenow variable)

add_action(
    'admin_menu',
    function () {
        global $pagenow, $typenow;

        if ( is_admin() && ! empty( $typenow ) && ! empty( $pagenow ) && $pagenow === 'edit.php' && stripos( $_SERVER['REQUEST_URI'], 'edit.php' ) && stripos( $_SERVER['REQUEST_URI'], 'post_type=' . $typenow ) ) {
            $pagenow = 'custom_post_type_edit.php';
        }
    }
);

This works without adding any PHP Notices, but may have unforseen issues as it is changing the $pagenow variable, but only on that page.

So far I am using Option 2 without any issues.