For Nahkchivan you're probably better off using local tourist agencies. Search for "nakhchivan tours" on the internet and you'll find a couple companies that can give you more listings than the major booking websites.
While this might not get you the cheapest accommodation, the thing with Azerbaijan is that there's this registration rule for visitors (see: https://caravanistan.com/visa/azerbaijan/registration/)
If your duration of stay is shorter than the registration timeframe then it's probably not an issue, otherwise the budget/family-run accommodations might not be doing the registration for you, and you risk getting fined when you leave the country (although I'm not sure how strictly enforced this is). This happened to me a few years ago when I had only 3 days to register but my hostel wouldn't do that for me. I wasted a whole day running between various super bureaucratic Azeri government agencies to try to get myself registered, who simply passes me around like a ball. Finally I walked into a fancy hotel asking for help and they point me to the right direction.
If you have a stay longer than the registration timeframe or have complicated logistics, go with a commercial hotel through a local travel agency. It might cost you around US$50-70 instead of the $15 budget hostels but the Azeri government is not something you want to deal with, especially if you're only there for a short time.