If your galleries are attachment
post types(?), then you could simply modify my "Internal Link Checker Plugin" to search only for galleries.
You need to change:
WHERE post_content
LIKE '%{$post->post_title}%' OR '%{$post->post_name}%'
ORDER BY post_date
to:
WHERE post_type = 'attachment'
This way you list the attached post types 'attachment' for the currently displayed post.
The shortcode has nothing to do with how the Media is stored in your database. It just cares about the display of the gallery.
Edit:
The following lines should give you all posts that have nggallery
in the post content.
WHERE post_content
LIKE '%nggallery%'
ORDER BY post_date
After finding and removing all those posts you can savely delete that table (I wouldn't do it before).