If MAX(id) != COUNT(id), does that mean rows have been deleted? The question pretty much says it all. We're talking MySQL here, version 5.1.

What I'm wondering is whether this would strictly means rows have been deleted, or if there are other possible scenarios that could cause this: weird locking or race conditions, etc. that force the table's ID counter to increment multiple times for a single insertion.
I assume you are asking about columns with the AUTO_INCREMENT property.

No, deleted rows is not the only reason, there are several others:


inserts that did not succeed (due to duplicate unique or primary key violations or other reasons).
inserts inside transactions that did not commit and were rolled back.
inserts where the id was explicitely defined (and id numbers were skipped or negative values added). In the second case, you can have MAX(id) less than COUNT(id) as a result. 
variation of the previous case: column was not AUTO_INCREMENT when the table was created - so there were explicit inserts for some period - and then modified.
updates of the auto-incrementing column.
the id was set to start from a value different than the default 1.
the auto_increment step setting (system variable: auto_increment_increment) of the server is not 1 (or had been changed to something else than 1 for some period).
and (something that is usually neglected because the id is usually the primary key), the column was not defined as the PRIMARY or UNIQUE key. That allows duplicates and one more case where the MAX can be lower than the COUNT.
a variation of the above is (with MyISAM engine) an auto-incrementing column that is part of a composite primary key.