It sounds like both your company and the well known one would both be in international class 41 for educational services. That company may also have a mark registered for their goods -books- as well, but all you care about is the class that's the same as your services. Trying to share a 1st word with a well known company within the same class can be risky, and as you know, anybody can claim anything. What you have to ask yourself is whether consumers are likely to be confused - will they find you when looking for them, or vice versa.
I don't think that your 1st words' lack of relationship with your services makes it unique, particularly if you share it with this company who got to the market before you. More importantly, do your mark's other words (or have you got just one more word?) make your mark distinguishable from that company's mark?
Just because the mark you're interested in doesn't turn up in the USPTO search or on search engines does not mean it's not one that infringes on someone else's rights, but it's a good start. Spending the money on a reputable search firm and experienced trademark attorney is a good idea to see what else is out there and get a fact-specific opinion about your proposed trademark.
Disclaimer: Please note that this answer does not constitute legal advice, and should not be relied on, since 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.
Query: Can well-known company claim infringement or dilution simply because the first name of our companies is the same?
You're on thin ice. Both you and the "well-known" company provide college admission advice. Both of your company names start with the same "unique" word. While adding these two facts together does not necessarily lead to a likelihood of confusion in the college admission advice marketplace it sure comes pretty close.
In most cases, and certainly in this one, seeking the advice of a trademark attorney BEFORE a company adopts a trade name or brand name makes much sense.
I suspect that if the well-known company does not have a federal registration, they might well have a state one. There are 50 states where they could have registered the name. You may need to do a name search on all of them. I am astonished that they do not have federal registration, but you are still liable for a trademark infringement suit because you are in the same business,In my home state there is a realtor named Century 21 and also a department store. There is no infringement because the two businesses are distinct and there can be no confusion in the marketplace. In your case there certainly can be confusion.
You might find my legal guide on selecting and hiring a lawyer helpful.
You might find my legal guide on Is it Legal? Is it Illegal? helpful.
You might find my legal guide on the understanding the different court systems helpful.
You might find my legal guide on legal terms used in litigation helpful.
(Even if you are not filing a lawsuit this information can be useful).
You might find my legal guide on commercial litigation helpful.
Mr. Sarno is licensed to practice law in NJ and NY. His response here is not legal advice and does not create an attorney/ client relationship. The response is in the form of legal education and is intended to provide general information about the matter in question. Many times the questioner may leave out details which would make the reply unsuitable. Mr. Sarno strongly advises the questioner to confer with an attorney in their own state to acquire more information.