SELECT COUNT(*) expensive query mysql?
"Will this query always be indexed AND fast as the rows in the table grow?"

Definitely not necessarily. If there are many records and/or the value of deleted is skewed in some way (i.e. it's (nearly) always one particular value, or split 50-50), then the optimiser may decide to ignore a given index. Googling "why does mysql not use an index" gives 3.5M results 

[EDIT]

You said:

"Thank you for your answer. Is there a different type of query I can use to count the number of rows with a WHERE clause?"

No -  that's what COUNT() is for. See here. Basically, you can't get round problems like the one you outline - indexes are frequently helpful, but there's no "magic bullet" that will cope well with all data volumes and profiles. 

To see how difficult this problem is, check here - that's > 600 pages on the fundamentals of how an RDBMS decides on the best plan for a query. It is far from a trivial problem!