I run a startup company. I thought i came up with a great product and everything was great. Then one day i received an email of someone claiming to have a PPA of that same product and to cease selling it or provide some form of royalties. I tried to work with them but this was there ultimatum. I was getting ready to sign a contract with them but i later found out they didn't even have a PPA for the product. It was one big deception in order to get me to pay royalties. I lost business because of this and want to know what are my option to deal with this legally?
Well, that business could be an exclusive licensee of the patent in question and have the right to sue or ask for royalties (sub license etc)
So, I think you need to ask for proofs that that company has those rights, in case they have you then should proceed to analyze if the patent apply to your case (check for a patent attorney)
ADDITION: But seen again your question, they only claim to have a Provisional Patent Application, if that is the case, you have to check the 35 U.S. Code § 154 (d) that covers the rights to collect royalties once the patent is issued for the time since the Publication of the Patent (not the issuing)
(...a patent shall include the right to obtain a reasonable royalty from any person who, during the period beginning on the date of publication of the application for such patent ....)
, but if that is the case, they need also to notify you about the patent:
(B)had actual notice of the published patent application and, in a case in which the right arising under this paragraph is based upon an international application designating the United States that is published in a language other than English, had a translation of the international application into the English language.
Even if the Provisional Patent Application exist, they need to wait until the publication of the patent to notify you of the existence of it, not before the publication date and then they need to wait until the issuing of the patent to collect those royalties.
But even if those events finally happens, the claims that the pending patent had on the publication date have to be identical to the claims of the finally issued patent:
(2)Right based on substantially identical inventions.— The right under paragraph (1) to obtain a reasonable royalty shall not be available under this subsection unless the invention as claimed in the patent is substantially identical to the invention as claimed in the published patent application.
So, they could be miss using the 35 U.S. Code § 154 (d) to get some money ahead of time. That could be the reason you did not find the provisional patent as it is not published yet (if it really exist at all)