OK, let me give a try on this question. There are several problems hidden underneath which one has to address.
First, for physical reasons a formal deformation is not sufficient. $\hbar$ is a constant of nature but not a formal parameter... More severely, the formal star product algebras do not allow for a reasonable notion of spectra and thus can not produce physically reliable prediction concerning possible values of measurements. For this (and many related reasons) formal deformation quantization is not the final answer.
Second, the $C^*$-world provides all we need for a good quantum mechanical interpretation: good notion of spectra compatible with a spectral calculus etc.
So in some sense, this is the situation we all want to reach: finding a $C^*$-algebra containing particular elements which have a physical interpretation. Note that just saying "this $C^*$-algebra is the algebra of observables of my system" is physically still meaningless. You have to specify an interpretation of which algebra element corresponds to which (physical) observable (ie. which, at least in principle, realisable measurement apparatus).
Third, and this is the bad side of the story: except for very simple situations (CCRs) it is very very hard to write down a $C^*$-algebra corresponding to a certain quantum system of which one only knows its classical counter part. So this is the problem of quantization: given a classical physical system, one wants to guess its quantum description. Of course, there are physically relevant situations where this is known and well-understood, but I'm taking here of more general classical systems: eg. for systems with gauge degrees of freedom, the physically relevant degrees of freedom form the "reduced phase space" which can carry an complicated geometry such that there are simply
no physical observables which allow for a simply CCR quantization.
Together, this indicates that the formal DQ might be not a solution but a first step: since for formal DQ one has very well-understood and powerful existence and classification results, one tries to use them and, as a second step, guess/construct the desired $C^*$-algebraic framework. But this is not at all easy.
So one way to go is to take the formal power series in the star product and ask for their convergence (in a mathematically meaningful way). This is tricky and has been achieved ony in (few) examples. In fact, I have some current projects in this directions. Ideally, one obtains a topological non-commutative algebra afterwards, which might not yet be $C^*$. But, and this is the first non-trivial step, it will be an algbebra over $\mathbb{C}$ and not just over $\mathbb{C}[[\hbar]]$. Of this algebra, one can then study HIlbert space representations by, in general, still unbounded operators. Arriving at this stage there are several standard techniques to build nice $C^*$-algebras out of it.
Why can one hope that this works? In those examples where one has a $C^*$-algebraic deformation in one of the many senses of "strictness",
it always involves some reasonable behaviour for $\hbar \to 0$. If one requires not just continuity, but some weak sort of smoothness, then one can "differentiate" the continuous field of $C^*$-algebras (from the right) at $hbar = 0$. This will give then a formal star product. As usual, one has only smoothness but not analyticity and hence the formal star product will not directly sum up to the continuous field of $C^*$-algebras. So in my opinion, this is the relation one can hopefully expect in quite some generality.
