From the MySQL 5.0 Reference:
Assessment of the nature of a routine is based on the “honesty” of the creator: MySQL does not check that a routine declared DETERMINISTIC is free of statements that produce nondeterministic results. However, misdeclaring a routine might affect results or affect performance. Declaring a nondeterministic routine as DETERMINISTIC might lead to unexpected results by causing the optimizer to make incorrect execution plan choices. Declaring a deterministic routine as NONDETERMINISTIC might diminish performance by causing available optimizations not to be used. Prior to MySQL 5.0.44, the DETERMINISTIC characteristic is accepted, but not used by the optimizer.
So there you have it, you can tag a stored routine as DETERMINISTIC even if it is not, but it might lead to unexpected results or performance problems.