Что использовать при кешировании запросов MySQL в PHP
Еще почитайте про redis. Сам его использую для кеширования. Может лучше подойдет вашему проекту, чем мемкеш.
насколько критично? как влияет на это то, что система многопользовательская?
кэшировать именно по запросам? может конкретные данные кэшировать?

>Но в этом случае придется решать проблему именно отслеживания изменений в таблице. 
так mysql именно это и решает, а вам это критично.