Computing colon ideals is pretty quick. You could colon out the variables in order. If the ideal changes, record the variable that worked, and go back to the beginning of the list. Either you get to the unit ideal, in which case you found the lex-first monomial that's in the ideal, or you make it to the end of the list, in which case there's no monomial in your ideal.

EDITS:

1. There's no need to loop back to the beginning of the list. Do $x_1$ to completion, then $x_2$, and so on.

2. Doing $x_i$ only requires a Gröbner basis for an elimination order for $x_i$, and the colon ideal will come with a Gröbner basis again, for free. So you don't even need a universal Gröbner basis, just $n$ elimination Gröbner bases.

3. You could also do this by coloning out $x_1 x_2 \cdots x_n$, which is very close to François Brunault's answer comment. But my understanding is that colon ideals are computed using the elimination of a new variable, so I doubt this is actually faster than what I'm suggesting.

4. You don't even need those full Gröbner bases, just ones that are Gröbner enough; see e.g. theorem 6.3 of http://arxiv.org/abs/dg-ga/9706003 where we use a criterion like this to compute a cohomology ring.

Computing colon ideals is pretty quick. You could colon out the variables in order. If the ideal changes, record the variable that worked, and go back to the beginning of the list. Either you get to the unit ideal, in which case you found the lex-first monomial that's in the ideal, or you make it to the end of the list, in which case there's no monomial in your ideal.

EDITS:

1. There's no need to loop back to the beginning of the list. Do $x_1$ to completion, then $x_2$, and so on.

2. Doing $x_i$ only requires a Gröbner basis for an elimination order for $x_i$, and the colon ideal will come with a Gröbner basis again, for free. So you don't even need a universal Gröbner basis, just $n$ elimination Gröbner bases.

3. You could also do this by coloning out $x_1 x_2 \cdots x_n$, which is very close to François Brunault's answer comment. But my understanding is that colon ideals are computed using the elimination of a new variable, so I doubt this is actually faster than what I'm suggesting.

4. You don't even need those full Gröbner bases, just ones that are Gröbner enough; see e.g. theorem 6.3 of http://arxiv.org/abs/dg-ga/9706003 where we use a criterion like this to compute a cohomology ring.

ANOTHER:

You could slice with random hyperplanes, and whenever you get isolated points, see if each of those points has some coordinate $=0$.

Computing colon ideals is pretty quick. You could colon out the variables in order. If the ideal changes, record the variable that worked, and go back to the beginning of the list. Either you get to the unit ideal, in which case you found the lex-first monomial that's in the ideal, or you make it to the end of the list, in which case there's no monomial in your ideal.

Computing colon ideals is pretty quick. You could colon out the variables in order. If the ideal changes, record the variable that worked, and go back to the beginning of the list. Either you get to the unit ideal, in which case you found the lex-first monomial that's in the ideal, or you make it to the end of the list, in which case there's no monomial in your ideal.

EDITS:

1. There's no need to loop back to the beginning of the list. Do $x_1$ to completion, then $x_2$, and so on.

2. Doing $x_i$ only requires a Gröbner basis for an elimination order for $x_i$, and the colon ideal will come with a Gröbner basis again, for free. So you don't even need a universal Gröbner basis, just $n$ elimination Gröbner bases.

3. You could also do this by coloning out $x_1 x_2 \cdots x_n$, which is very close to François Brunault's answer comment. But my understanding is that colon ideals are computed using the elimination of a new variable, so I doubt this is actually faster than what I'm suggesting.

4. You don't even need those full Gröbner bases, just ones that are Gröbner enough; see e.g. theorem 6.3 of http://arxiv.org/abs/dg-ga/9706003 where we use a criterion like this to compute a cohomology ring.