The lack of a search feature in NextGen gallery creates a bit of a problem for us, now that there are over 4000 pictures in the galleries. After a considerable amount of banging my head against a wall I have a query that I can run against both the images table and the custom fields table and return sensible values. For posterity, this is the query (looking for 'currie'):

SELECT pix.pid,pix.galleryid,pix.description,pix.alttext,ref
FROM wp_ngg_pictures pix
INNER JOIN (
   SELECT cf.pid,group_concat(cf.field_value)AS ref
   FROM wp_nggcf_field_values cf
   GROUP BY cf.pid
   ) cfv ON pix.pid = cfv.pid
WHERE (
   pix.description LIKE '%currie%' OR 
   pix.alttext LIKE '%currie%' OR 
   ref LIKE '%currie%'
)
ORDER BY pix.galleryid ASC

Next up is to figure out how to create an on-the-fly gallery out of the results that looks and feels like the other galleries.