We consider certain functional identities on the matrix algebra $M_n$ that are defined similarly as the trace identities, except that the "coefficients" are arbitrary polynomials, not necessarily those expressible by the traces. The main issue is the question of whether such an identity is a consequence of the Cayley-Hamilton identity. We show that the answer is affirmative in several special cases, and, moreover, for every such an identity $P$ and every central polynomial $c$ with zero constant term there exists $m\in\mathbb{N}$ such that the affirmative answer holds for $c^mP$. In general, however, the answer is negative. We prove that there exist antisymmetric identities that do not follow from the Cayley-Hamilton identity, and give a complete description of a certain family of such identities.

Version 2: 24 pages. This paper is a replacement of the paper "Quasi-identities and the Cayley-Hamilton quasi-polynomial" by the first and the third author. The changes are substantial. Version 3: 27 pages. The title has been changed slightly, the exposition improved, references added, and some typos removed