MySQL Deterministic Procedures
It makes sense to use the deterministic keyword for procedures that are really deterministic, because:


  Declaring a deterministic routine as NONDETERMINISTIC might diminish
  performance by causing available optimizations not to be used.


But:


  Am I right in thinking that the only non-deterministic procedures are
  ones that call non-deterministic functions like RAND() or CURDATE()?


No, a procedure that reads data from the database and bases it's result on that data (in addition to it's inputs) is also non-deterministic (because that data might change between calls).

It is worth pointing out that whether a procedure is DETERMINISTIC or not needs to be considered in a replication context:


  When you create a stored function, you must declare either that it is deterministic or that it does not modify data. Otherwise, it may be unsafe for data recovery or replication.


although:


  If row-based or mixed binary logging is in use, the statement is accepted and replicated even if the function was defined without the DETERMINISTIC keyword.