While trying to remove broken releases (that can't be edited, due to MBS-1929) I tried to search for releases with no mediums:

http://musicbrainz.org/search?query=mediums%3A0&type=release&limit=25&advanced=1

It's possible to search for mediums:1 etc; but not zero.

It's also possible to search for releases with no tracks:

http://musicbrainz.org/search?query=tracks%3A0&type=release&limit=25&advanced=1

So I think the above mediums search should work; even though in an ideal world no such releases should exist in the database; and with the fix to MBS-2035 fewer should. If this is an easy fix on the search server, this would save writing a report, perhaps?

Also worth noting that releases without mediums don't show up on the tracks:0 search either; I'd expect them to be on both.