For this issue in general, I think you have to make the additional distinct query upfront:
var actualResultCount = session.Query<Restuarant>().Where(x=> x.Promotions.Any(y=> y.City == "New York" && y.Food == "Pizza")).Select(x=>x.RestID).Distinct().Count();
While that number gives you a realistic total, you will still have issues with non-sequential paging because you don't know where the skipped results are located until you get each page.
For the specific SO question, assuming the fields to query are always the same you could do some domain specific encoding for the index:
from rest in docs
select new
{
rest.RestName,
CityTypeFood= rest.RestPromotions.Select(x=> string.Join("|", x.City, x.Type, x.Food))
}
Then querying on the joined index field will still provide an accurate TotalResults value:
var lookup = string.Join("|","New York","Italian","Pizza");
var results = session.Advanced.LuceneQuery<Restaurant, RestaurantIndex>().WhereEquals("CityTypeFood",lookup);
The string join encoding only works if you are always querying all of the same fields, but you could probably concoct other encodings to handle more complex queries (e.g. flags enum emulation)