I stopped using NextGen galery becaused it slowed my site bigtime, so I deleted the plugin and the galleries folders, but tons of crap remained at the MySQL database.
I came up with these queries to get rid of it:
DELETE FROM wp_pf_posts WHERE post_type like 'ngg_%' or post_title like '%ngg%' OR post_title like 'NextGen_%';
DELETE FROM wp_pf_options WHERE option_name like '%ngg%' OR option_value like '%ngg%';
DELETE FROM wp_pf_postmeta WHERE meta_key like '%ngg%' OR meta_value like '%ngg%' OR meta_value like '%NextGen%;
I successfully got rid of around 1500 useless rows and my DB file is considerably smaller.