The present paper produces examples of Gauss diagram formulae for virtual knot invariants which have no analogue in the classical knot case. These combinatorial formulae contain additional information about how a subdiagram is embedded in a virtual knot diagram. The additional information comes from the second author's recently discovered notion of parity. For a parity of flat virtual knots, the new combinatorial formulae are Kauffman finite-type invariants. However, many of the combinatorial formulae possess exotic properties. It is shown that there exists an integer-valued virtualization invariant combinatorial formula of order n for every n (i.e. it is stable under the map which changes the direction of one arrow but preserves the sign). Hence, it is not of Goussarov-Polyak-Viro finite-type. Moreover, every homogeneous Polyak-Viro combinatorial formula admits a decomposition into an "even" part and an "odd" part. For the Gaussian parity, neither part of the formula is of GPV finite-type when it is non-constant on the set of classical knots. In addition, eleven new non-trivial combinatorial formulae of order 2 are presented which are not of GPV finite-type. © 2012 World Scientific Publishing Company.