Incorporated name constitutes trademark infringement?

You need to talk to a trademark attorney, and they'll need specific facts.

They may have been registered the mark in 2005 but doing business using that mark as a source indicator well before that (perhaps even before 2000 when you registered your company name). You haven't provided enough information here to determine that, and who has first use the mark in commerce will have superior rights to use that mark within the geographical region that they are doing business. I think this is going to be one of the primary issues that needs to be teased out. The other issue is whether you may still have regional rights to use that mark - if you were first to use that mark in commerce and didn't register it federally, you may have superior rights based on state laws.

Depending on where you each do business, you may be able to peacefully coexist provided that there won't be actual or likely confusion about the source of goods and services. There is also the possibility that their trademark is legally invalid. A trademark attorney can sort this out pretty quickly and figure out the most effective way to deal with this.

Mr. Phillips' analysis is absolutely correct. I join in his answer.

Your company name was registered as a corporation in 2000, but that has nothing to do with whether you used it as a trademark or not, and if you did use it, how and where you used it (and whether you also had the same domain name). You don't provide any facts about whether this DE company has a federal or a state registration, and how and where they've been using their mark. You don't provide any details about what this cease and desist says, and why they're claiming that your company name infringes on their trademark.

You've stated that your company and the DE company are in the same hardscape business, so a consumer might be confused if your company name and their trademark sound and/or look similar enough to be confusing.

But the strength of any infringment claim is a fact-specific analysis that can't be done with incomplete facts such as this case.

See an IP lawyer so you can disclose everything and get some specific advice.

Disclaimer: Please note that this answer does not constitute legal advice, and should not be relied on, since each state has different laws, each situation is fact specific, and it is impossible to evaluate a legal problem without a comprehensive consultation and review of all the facts and documents at issue. This answer does not create an attorney-client relationship.

See http://bit.ly/3XGa2D for responses to a similar question.