In [J. Phys. A: Math. Theor. 45 (2012)], while looking for spin chains that admit perfect state transfer, Vinet and Zhedanov found an apparently new sequence of orthogonal polynomials, that they called para-Krawtchouk polynomials, defined on a bilinear lattice. In this note we present necessary and sufficient conditions for the regularity of solutions of the corresponding functional equation. Moreover, the functional Rodrigues formula and a closed formula for the recurrence coefficients are presented. As a consequence, we characterize all solutions of the functional equation, including as very particular cases the Meixner, Charlier, Krawtchouk, Hahn, and para-Krawtchouk polynomials.