"Vereenigde Oost-Indische Compagnie" (United East India Company), and so would never even have been near the Caribbean.
That is incorrect. The original goal of the EITC was to sail to the Indies, but they quickly expanded their area of operations due to their vast success.
The East India Trading Company, otherwise referred to as the East India Company or abbreviated as EITC, was a British joint-stock company and megacorporation formed for pursuing and monopolizing trade with the Indian subcontinent and East Indies, and later expanded to China and the Caribbean.
Link
Secondly, the first movie establishes that Jack Sparrow has run into the EITC before:
[Notices Jack's brand] "Had a brush with the East India Trading Company, did we, pirate?"
―Commodore James Norrington to Jack Sparrow
Even if the EITC hadn't branched out to the Caribbean yet, Jack Sparrow would still have had dealings with them abroad, thus suggesting that Jack could plausibly have interacted with the "real" Flying Dutchman.
But we know that the EITC was branching out to the Caribbean, since Lord Cutlers Beckett makes his first appearance in Dead Man's Chest as Chairman of the East India Trading Co.
Thirdly, I see no reason to focus solely on the Caribbean. The last movie of the trilogy specifically shows us that the Brethren's Court is an international collection of pirates.
Jack Sparrow, Hector Barbossa, and Elizabeth Swann (Sao Feng's successor), as well as Chinese Mistress Ching, Indian Sri Sumbhajee Angria, African Gentleman Jocard, Turkish Ammand the Corsair, Spanish Eduardo Villanueva, and French Capitaine Chevalle
Link
In this international collection have the Carribbean, Singapore (Elizabeth is not Singaporean but Sao Feng was, and her crew still is), China, India, Africa, Turkey, Spain and France. Pretty much every globally significant empire (barring the British, which are arguably represented by Barbossa and Sparrow).
The EITC and by extension Davy Jones were a global problem, not just a Caribbean one.
In Pirates of the Caribbean, Davy Jones is called captain of the Flying Dutchman, the ship is a mean to ferry the souls of the dead, gifted to him by Calypso.
The first question that enters my mind: where did Calypso get the ship from?
Even if you follow its supernatural origin story, it's perfectly possible that the goddess of the sea was somehow involved, or at the very least capable of reappropriating the ship to Davy Jones' control.
Secondly, there is no mention of the "real" legend of the Flying Dutchman in the movie universe. It's perfectly possible that the fictional movie universe diverges from the real world in this regard.