Recently Kontsevich solved the classification problem for deformation quantizations of all Poisson structures on a manifold. In this paper we study those Poisson structures for which the explicit methods of Fedosov can be applied, namely the Poisson structures coming from symplectic Lie algebroids, as well as holomorphic symplectic structures. For deformations of these structures we prove the classification theorems and a general a general index theorem.