I think that caching, regardless of multi-tenant or not, doesn't really matter if you follow certain practices.
For example, I avoid using static strings as my cache keys. I.e., "users_list" would be a poor choice for a cache key as it would be a "global" return. Always scope in the account for something like this; for example, [account.id, "users_list"]. You could use [account, "users_list"], but you have to ask yourself if this list should be immutable if data on the account changes. It has to be handled on a case by case basis. In the account.id example, if you have new users added to the list, the cache will not update. In the later example of account being in the cache key, if you update the name of the account, it will also invalidate the cache which wouldn't be desirable or accurate since you'd then be querying the database more often.
Likely, I would take the most simplistic approach with caching the individual records. If I outgrow this solution, I would then implement something like Russian Doll Caching. I would start simple because the more caching you add into your application, the greater chance of something "strange" going on. It's best to ease into caching and really put it in place where it is needed.
I don't think I have an episode for Russian Doll Caching, so I think that this suggestion would be a good fit for that. But, I would likely follow this methodology regardless of it being for a multi-tenant solution or not. On a side note with multi-tenant solutions, I never search off of the base class. For example, I don't do a User.find(X). I would always do something like current_account.users.find(X). This will inherently prevent the cross talk between accounts that you mentioned.