Where do pending drush database updates live?
Drupal will look in /modules and /sites/*/modules if the site was installed on top of the default profile. If you're using a distribution or other contrib/custom profile then it'll also look under /profiles/[name-of-profile].

SELECT filename FROM system WHERE name = 'video_embed_field'


will tell you exactly where Drupal is looking for the module you're trying to find.


  Are these database updates stored in a table in the database[?]


I haven't looked at Drush, but as far as core's update.php goes, no. The .install file of each enabled module is checked to see if it has any update functions with a schema greater than the currently installed schema. I'd imagine Drush does the same thing, no real reason for it to do things differently.

If that assumption holds, then you basically couldn't be seeing those updates as options unless the module is somewhere in the file system (or at least a PHP file that will be included in a normal bootstrap containing a function called video_embed_field_update_7123() or similar).

So keep looking, it's likely to be there somewhere!