Hey @CSiragaki loved your line of business (grandson of a a codfish captain here!).
You need to create a workflow on the object you can re-enroll (i.e: if you build a company workflow the trigger can’t be “new vessel name is known” because that can’t be used for re-enrollment since it’s a property of an associated custom object and not the main object of that workflow).
Assuming that your deal <> company association is built first we need to create a custom property that would be used to make the association between Vessel <> Deal later.
1) Build a Deal workflow that everytime it has a new company associated it will get the company name of that company and copy to a new custom property you created called “Primary Company Name”
2) On the Custom Object creation set as required to associate a company
2.1) Than build a Custom Object (Vessel) workflow that will trigger everytime Vessel name is known.
2.2) First go get the Associated company name and add it to a property you created called “Primary Company Name” and voilá you know have a matching property with the deal you want to associate (check the example below - vessel it’s entinty in this print)
3) Add that “create associations” action set it to associate with deals, using “matching property values” and use the properties you created beforte “Primary Company Name” to match both - Than it’s up too you to pass whatever you need to that deal 