Edit In my previous answer I took $M$ to be the set of elements with image $\{2,\dots, n\}$ toegther with a random involution. In fact, that answer does not produce a monoid, since the square of an involution is the identity $\text{id}$ which was not an element of the monoid defined.

Here is a correct answer. Take $M\subset \text{Self}(\{1,\dots, n\})$ to be the set consisting of the identity, and the set of elements that have image in $\{\lfloor n/2\rfloor, \dots, n\}$. Let $\sigma$ be a perfect hash on involutions that are the identity on $\lfloor n/2\rfloor, \dots, n$. Let $M_\sigma$ be the monoid consisting of $M$ and the involution $f_\sigma$ with $\sigma(f_\sigma) = 0,$ if it exists. Then you can check that $M$ is always a monoid, but you can't compute $f_\sigma(1)$ in polynomial time.

Note With the current formulation of your question, it is actually enough to take $M$ to be $\text{id}$ and a random involution determined by a perfect hash. In a previous version, you asked that $M$ be enumerable in a length of time which is polynomial in $|M|,$ and adding in all elements with image $\{\lfloor 1,\dots, n\rfloor\}$ guarantees this.

Edit In my previous answer I took $M$ to be the set of elements with image $\{2,\dots, n\}$ together with a random involution. In fact, that answer does not produce a monoid, since the square of an involution is the identity $\text{id}$ which was not an element of the monoid defined.

Here is a correct answer. Take $M\subset \text{Self}(\{1,\dots, n\})$ to be the set consisting of the identity, and the set of elements that have image in $\{\lfloor n/2\rfloor, \dots, n\}$. Let $\sigma$ be a perfect hash on involutions that are the identity on $\lfloor n/2\rfloor, \dots, n$. Let $M_\sigma$ be the monoid consisting of $M$ and the involution $f_\sigma$ with $\sigma(f_\sigma) = 0,$ if it exists. Then you can check that $M$ is always a monoid, but you can't compute $f_\sigma(1),$ and hence the image of $M_\sigma,$ in polynomial time.

Note With the current formulation of your question, it is actually enough to take $M$ to be $\text{id}$ and a random involution determined by a perfect hash. In a previous version, you asked that $M$ be enumerable in a length of time which is polynomial in $|M|,$ and adding in all elements with image $\{\lfloor n/2\rfloor,\dots, n\}$ guarantees this.

Turning my comment into an answer to the current formulation since it's a bit on the long side. The answer is no: you might have a characterization which is not polynomial time in n. For an example, let $M_0$ be the monoid of all self-maps with image in $\{2,\dots, n\}.$ Let $$M' = \{f\in \text{Self}(\{1,\dots, n\})\mid f(1) = 1, f\,\text{is an involution}\}.$$ Let $$\sigma: M_0\sqcup M'\to M_0\sqcup M'$$ be an invertible hash function that can be computed in polynomial time in $n$. Now consider the element $f_\sigma: = \sigma^{-1}(\text{id}) \in M_0\sqcup M',$ and define the monoid $M_\sigma: = M_0\cup f_\sigma.$ The element $f_\sigma$ is either in $M$ or in $M'$, and depending on this, the monoid $M_\sigma$ either has image $\{2,\dots, n\}$ or $\{1,\dots, n\}.$ Checking whether a given element is in $M_\sigma$ is polynomial time in $n$ (you know it is in $M_\sigma$ if either it is in $M_0$, or if it is an involution with $f(1) = 1$ and $\sigma(f) = \text{id}$). However (at least under standard cryptographic assumptions), there is no polynomial-time algorithm for determining whether $f_\sigma$ is in $M'$ (since both $M$ and $M'$ have superexponential size in $n$).

Edit In my previous answer I took $M$ to be the set of elements with image $\{2,\dots, n\}$ toegther with a random involution. In fact, that answer does not produce a monoid, since the square of an involution is the identity $\text{id}$ which was not an element of the monoid defined.

Here is a correct answer. Take $M\subset \text{Self}(\{1,\dots, n\})$ to be the set consisting of the identity, and the set of elements that have image in $\{\lfloor n/2\rfloor, \dots, n\}$. Let $\sigma$ be a perfect hash on involutions that are the identity on $\lfloor n/2\rfloor, \dots, n$. Let $M_\sigma$ be the monoid consisting of $M$ and the involution $f_\sigma$ with $\sigma(f_\sigma) = 0,$ if it exists. Then you can check that $M$ is always a monoid, but you can't compute $f_\sigma(1)$ in polynomial time.

Note With the current formulation of your question, it is actually enough to take $M$ to be $\text{id}$ and a random involution determined by a perfect hash. In a previous version, you asked that $M$ be enumerable in a length of time which is polynomial in $|M|,$ and adding in all elements with image $\{\lfloor 1,\dots, n\rfloor\}$ guarantees this.