Steve, just guessing but I would think that if the notification of the marriage has not reached NSO then they would have no record of. It would seem that it cannot be they don't have any records of your wife because, as you said, she got the copy Birth Cert.
We collected the notice from the Registrar's office of the town hall and sent it by courier (LBC) to speed things up.
