We provide a deep investigation of the notions of 𝒢- and $𝒢^∞$-hypoellipticity for partial differential operators with constant Colombeau coefficients. This involves generalized polynomials and fundamental solutions in the dual of a Colombeau algebra. Sufficient conditions and necessary conditions for 𝒢- and $𝒢^∞$-hypoellipticity are given