Why pagination is not working with tax_query param?

I’ve found the solution by myself. In brief: use 'order' => 'DESC'


The long story:

Since I was doing the first page query via php (standard loop), and instead, the above is done via ajax, passing pagination (thus page 1 is php, the following are ajax), there was a mismatch about the order.
I was still retrieving what is seemed to be page 1 posts because the query was done with the default ASC order, while the standard loop works with DESC order by default (date-based). So the posts retrived by ajax were in fact of page 2!

By inverting the order, I now get the right posts.