Membership doesn't work correctly with Directory

I provide access to a Directory plugin pages to my premium members and access is managed by Membership plugin.
After we added lots of listings to a Directory our members started to send us a complaints that they cannot access certain pages of the directory.
We discovered that it is about /listings-category/some-category-name/ pages. Members can browse only first page of each category, when they try to open next pages the site returns 404 error.
Links to that pages look like /listings-category/accessories/page/2/
It seems the problem is in that /page/2/ part of URI.
I tried to disable Membership for a second. All pages are showing fine with Membership turned off.
Please advice how to make those page work with Membership enabled.