This is a tricky question and there is a whole area of research dedicated to solving it. The definition of the thermodynamically stable phase of a system is that occupying the global minimum of the potential energy surface, or more precisely, the global minimum of the potential free energy surface at the temperature of interest. Let me focus on solid phases, and divide the answer into two cases:
Elemental compounds. For compounds containig a single element, then the question simply becomes: what is the structure that has the lowest energy? As trivial as this question may sound, it has no general solution. In principle you should try all possible structures (with any number of atoms in the primitive cell) in all possible atomic arrangements to find the global minimum. This is a computational problem with exponential scaling, so it has no solution. Although there is no general answer, the past 15 years or so have seen great progress, with DFT-based structure prediction methods using a variety of algorithms (stochastic, genetic, etc.) capable of exploring many structures and providing reasonable answers to the question posed. Despite the success of these methods, note that they do not provide a general solution: to give an example, structure searches are limited to about $100$ atoms per cell, but it could very well be that the primitive cell of a material has $1000$ atoms per cell, which means that the structure could never be found unless that many atoms are used in the simulation.
Non-elemental compounds. For compounds with more than one element, you need to add an extra degree of freedom to the search space: the stoichiometry of the compound. What you should do is the same structure searching in point 1, but now for every possible stoichiometry. Again, it may be that the correct stoichiometry is one you never try, so you would completely miss the thermodynamically stable structure in this case.
Up to this point, I have discussed the difficulties in scanning through all possible structures, arising from the extremely high dimensionality of the structural and composition spaces of materials. But let's imagine you have gone through the exercise of generating a range of candidate structures for your system. Then the next step is to figure out which one is the lowest (free) energy structure. The first step taken is typically to do a static lattice DFT calculation, which gives the electronic contribution to the energy. Then a finite temperature calculation is done to include the vibrational contribution to the energy at a given temperature. This calculation can be done either using the harmonic approximation to lattice dynamics (phonons), or a molecular dynamics simulation as you described. The former is fine at relatively low temperatures for most materials, and the latter necessary at higher temperatures when anharmonic vibrations become important.
The free energies you get from these calculations allow you to decided which is the lowest energy of your elemental system (for example if you do this for carbon, you will find that graphite is the ground state as it has a lower energy than diamond), and it will also tell you the correct stoichiometry of a compound by building the corresponding Hull diagram (as you pointed out, this is being done in the Materials Project). To be precise, these calculations will tell you what the lowest free energy structure/compound is amongst those you try. However, remember that you can never be sure that you didn't miss a lower energy material in your initial searches.
At this point the situation may look desperate. However, in practise it is many times possible to determine the actual thermodynamically stable structure. The obvious answer is that there may be experimental data. Even if there is only partial experimental data (for example no hydrogen positions, which are difficult to determine using X-rays), then these experiments can provide important constraints that can guide the theory and dramatically reduce the dimensionality of the search space, for example by providing the space group of the material. Finally, even if there is no data, many systems adopt relatively high-symmetry structures with relatively few atoms in the primitive cell. This makes the structure searches easier, as symmetry constraints reduce the dimensionality of the space being explored, and small primitive cells maximize the chances that you are exploring the correct number of atoms in the primitive cell. Indeed, structure prediction has been able to predict multiple structures that have subsequently been confirmed experimentally.
