We show how combinatorial star products can be used to obtain strict deformation quantizations of polynomial Poisson structures on Rd, generalizing known results for constant and linear Poisson structures to polynomial Poisson structures of arbitrary degree. We give several examples of nonlinear Poisson structures and construct explicit formal star products whose deformation parameter can be evaluated to any real value of ħ, giving strict quantizations on the space of analytic functions on Rd with infinite radius of convergence. We also address further questions such as continuity of the classical limit ħ→ 0 , compatibility with ∗-involutions, and the existence of positive linear functionals. The latter can be used to realize the strict quantizations as ∗-algebras of operators on a pre-Hilbert space which we demonstrate in a concrete example.