mysql statement based replication - unsafe statements
It will probably cause differences on the slave in the long run. I've had the same warnings (but with INSERT DELAYED, so your mileage may vary), and on a couple of write intensive tables the data would be different a couple of times a week (leading to a lenghty dump and import).

The ordering of some things is not necessarily the same on every mysql server, so you might end up with the same data in a different order. This is what "not deterministic" means, you execute the exact same query, but you might end up with different results.

If your mysql version supports the MIXED mode for binlogging, I'd definitely use that. 
As you can see on http://dev.mysql.com/doc/refman/5.1/en/binary-log-formats.html, the only reason it's not MIXED by default is backward compatibility:


  Support for row-based logging was added in MySQL 5.1.5. Mixed logging
  is available beginning with MySQL 5.1.8. In MySQL 5.1.12, MIXED become
  the default logging mode; in 5.1.29, the default was changed back to
  STATEMENT for compatibility with MySQL 5.0.


MIXED mode uses STATEMENT mode binlogging (the default), unless it knows the query is non deterministic, then it'll switch to ROW mode for those queries. With ROW mode, it simply sends the changed rows if any, so that's deterministic again.