Fedosov's work seems to be also available with details in a book Deformation quantization and index theory. Are the two references overlapping ?
Yes, indeed. The book contains strictly more than the contents of the paper from 1994.
I've found several documents from Kontsevich having similar titles, from 1997 to 2003, but I've no access to the reference of 2003, is the arXiv version the same as the final one ?
Again, yes. The preprint from 1997 is essentially the same as the paper published in LMP in 2003.
I'd like to understand whether these two works are equivalent or not, if they overlap somehow, and which kind of problem these works solved.
As it is explained in the comment by Bertram Arnold, Fedosov's quantization works for symplectic manifolds only (and can actually be generalized to regular Poisson manifolds) while Kontsevich's quantization works for general Poisson manifolds (even the ones having non-regular symplectic foliation).
In the symplectic case, the local deformation quantization is known to exist, and is essentially unique (it's the Moyal-Weyl star-product). So, the deformation quantization problems is a globalization problem, that is solved by Fedosov using methods from formal geometry and homological algebra.
In the general Poisson case, even finding a local formula is a difficult task. This is actually the most difficult part of Kontsevich's theorem. Once this is done, one proves that the local formula satisfy certain property that allows to run a globalization precedure that is similar to the one used by Fedosov.
Hence, Kontsevich's result definitely encompasses the one of Fedosov.
which kind of problem these works solved
Fedosov's work solves the problem of finding a star-product quantizing the Poisson bracket for functions on a symplectic manifold.
Kontsevich's work solves the far more general problem of finding a star-product quantizing the Poisson bracket for functions on a Poisson manifold.
Concerning the path integral approach to deformation quantization (work of Cattaneo--Felder), that is mentionned in Bertram Arnold's comment, Kontsevich's approach relies on a Sigma model with 2d source/worldsheet (the so-called Poisson sigma-model), while Fedosov's procedure can be unerstood as relying on a sigma model with 1d source/worldsheet (see e.g. Cattaneo's Part III of Déformation, quantification, théorie de Lie -in English despite the french title-, Chapters 10-11, or the more recent work of Grady--Li--Li https://arxiv.org/pdf/1507.01812.pdf).