A block created with Views is not rendered if the page URL contains "page="
I think I worked out what the problem was. The way the View selected the content, there could only be one result (the View is to show the current exhibition for an art gallery website, and they only ever have one exhibition at once). Because by design it could only produce one result I didn't even think about the pager, which was to Full by default. 

This caused problems when that block was rendered on the same page as another View - one which deliberately has a pager. Maybe there's an issue with multiple pagers on the same webpage?

Anyway, I changed the block View's pager settings to "Display a specified number of items | 1 item" and that fixed everything - now there's only ever one pager on the webpage and now my block view is displayed on every page as it's supposed to.

Edit: Will click this as accepted answer in 2 days when I'm allowed to