Rudy -
You're right about LIKE '2004-03-%' not using an index; I have tested it. I stand corrected. (Though, it's surprising the optimiser is not clever enough to convert that expression to a date range comparison). If it was a string field being compared, then an index would presumably be used.
When I said dates are stored as 'YYYY-MM-DD', what I meant was that as far as the normal user is concerned, that is how they might as well be stored, because that is how they are always presented to the user (of course, you can also use 20040301 and '20040301'), regardless of the internal storage format. The point I was making was that a MySQL date field is never accessed in the form M/D/Y. Judging by the nature of the question, I thought a simple (though possibly simplistic) answer would be appreciated.
In any event, maybe we're both barking up the wrong tree; maybe "ajuly"'s field is not a standard DATE field, as he/she implies.