Just a note that in 2013 SP1 the 'Where used / Published to' can sometimes be empty initially (when opening the dialog). This behavior only occurs sometimes and a simple refresh helps load the items, however, as you're experiencing 404s the Pages indeed seem missing instead of the dialog not listing them.
Are there any circumstances under which the page would still show as
published under the 'Published to' tab, but where the page is not live
on the listed target?
Under normal circumstances, no! However, there can be some inconsistencies between the published states and the actual published content because of some anomalies in the publishing process. Again, this is not normal behavior, and these orphan items need to be resolved.
In your case, you can simply unpublish the page from the given Target. This will cause the publish state on the CM to be set to 0, the CD side will be unaffected as the Page is already not there.
PS. Some shameless self promoting, but you can take a look at my TDS talk here which is about these orphan items and how to address them.