Yur domain registration has a date.
Their business registration (dba) has a date.
As long as yur domain registration pre dates their dba you win!
I HIGHLY suggest you hire an attorney to simply write them the letter.
That legal letterhead works wonders.
Plus an attorney will be able to quote the legal penalties for infringement to them and make em wet thier pants!
Also Google the legal forums for free legal advice.
Good luck bro!