Can exhaustive algorithms produce MSAs that are suitable for 3D structure modelling?
No. 

Methods for multiple sequence alignment (MSA) like T-coffee, which you mention, and Clustal (http://www.clustal.org), which is also widely used, employ heuristics for the alignment for the very good reason that exhaustive algorithms to do this are NP-complete.

You mention the dynamic programing algorithm as exhaustive in your comment. Alignment of two sequences by dynamic programming has an order of time complexity (big O) of $n^2$ and may take a few minutes depending on sequence length etc. Alignment of three has a big O of $n^3$ and can be done if you have lots of time on your hands, but it should be obvious that that's the limit to the number of sequences that can be aligned using dynamic programming.

There's no shame in heuristics. Perhaps the most widely used bioinformatics program in the world, BLAST, employs a heuristic. (And your brain makes decisions that your life depends on every day using heuristics.)

The methods that use heuristics for MSA have been successively modified to deal with known factors that can cause problems, so often they perform very well. How can you tell? What you need to do in using MSA programs is to perform a "sanity check" on any alignment that the programs produce — does it look reasonable, has it matched up similar regions well or are there vast gaps introduced or obvious regions of homology missed. And if you are doing 3D modeling and you don't get an alignment that looks good, then your modelling isn't likely to work. 

Finally you always have to consider the possibility that there aren't any proteins of known structure that are similar to the one you want to model so you'll never get a good MSA.