Received recently because of a new domain name registration (they're using automated scripts to find new registrations and potential victims), was the following message, claming potential late fees and more if I don't register the domain with the search engines using thier site. Blatant scam using scary phrases to catch you and part you from your money. 

-- begin email --

To: [you@yourdomain.tld]
Subject: REMINDER: Search Engine Registration for Your Domain [your-new-domain] is pending

Hi there [name from new domain registration record],

Domain Name: [your-new-domain] (Account #64232)
This email is being sent out to you because search registration for [your-new-domain] is pending.
Please register these domains to search engines like Google, Bing and Yahoo ASAP to avoid late fees.

Registering for search engines would help you show up in search results and increase your online presence.

You can register your domain at: [link to scammers site]

We sincerely appreciate your business! If you require anything, we are at your service.

Remember
If you do not register your domain with the search engines, it may not appear in the search engine listing when people are looking for you. Failure to complete your domain name search engine registration by the expiration date may make it difficult for your customers to locate you on the web. Complete your search engine registration today at: www.[scammers-domain].org [the actual link was not to this domain they own, it was to the scammers throwaway domain, along with tracking code]
Sincerely,

Search Engine Registry
1787 Pennsylvania Ave NW, Suite 1025
Washington DC, 20006

-- end email --

"searchregistry.org" is a very new domain (April 2014), likely their own, and extremely unlikley to have a Washington DC address.
There are no fees to get search engines to find you, so no chance of "late fees" or "penalties". At the bottom of thier website is a link to a disclaimer, and it begins with this:

"DISCLAIMER:

The information contained on this mailer and advertising material is for your general information and/or advertisement purposes only. SearchRegistry ( SearchRegistry.org) is a one time service to customers, whereby SearchRegistry will submit customer's registered domain to search engines to get customer's website listed on various search engines. "

Mailer? This was on the website, so they're attempting to answer for the email that got you there, in hidden fine print you need to click a specific link to see.
By all means, ask us about any such emails you receive, and we'd be happy to help you confirm or deny validity.