I am not stating that they are or are not legitimate, only that I found nothing that indicated a mystery shopping company in NYC by that name or reference to such a company. You ultimately need to use your common sense. It may be legitimate and is more likely to be so if:
1) They are not suggesting fees of more than $20-25 max per job.
2) They are referring you to a website to register as a shopper (i.e. not asking the information in an email).
3) The email comes from a business address, not a Yahoo or Gmail or Hotmail or AOL etc. account.
4) They disclose to you in the email how they contacted you ("Suzy at XYZ where you are signed up as a shopper indicated to us that you shop the ____ area."
A lot of scammers are using the names of legitimate companies just slightly altered to contact folks. Do not use the links they provide to their 'company' if you can get around it by googling and finding the real company by that name.
A "blind" email asking for your personal information is guaranteed to be a scam, and by "blind" I mean one with folks that you have not previously contacted.
Offers of payment up front for shops does not happen with legitimate companies unless you have worked with them extensively and it is the only way you would be able to perform the shop. Common sense--would you send $ to a 'potential employee' in hopes they would show up for work next week? On the other hand if a trusted employee's car broke down you might advance him next week's pay to get it fixed so he could show up for work.