I've tried \nopagebreak in the definitions of \itemdecl and \itemdescr, but to no avail (i.e. no effect shows up). It appears I can relax the page break penalty before \itemdecl, but that just causes lone headings. And the end of the \lstnewenvironment seems particularly hostile to adding a \nopagebreak.

Ah, suggesting a \pagebreak at the end of an \itemdescr seems to do some good.

Re: suggesting a \pagebreak at the end of an \itemdescr seems to do some good

Not so, it just makes index entries have off-by-one errors in the page number, apparently when the \itemdecl is preceded by \index stuff.

After some further experimentation, it seems we should enable \raggedbottom. For example, \itemdescr uses the indenthelper environment, which seems to have nearly zero stretchable vertical space. (I'm actually wondering why we're using that particular path to indent an area of text.)

My theory is that with zero vertical stretchable space, we often run into the situation that there are several page break scenarios that are all infinitely bad, so TeX picks a random scenario (which could mean a lone section heading at the bottom of a page).

@tkoeppe: Any opinions on \raggedbottom?

https://tex.stackexchange.com/questions/35933/indenting-a-whole-paragraph
has ideas on indenting text, the simplest of which changes \leftskip (idea: put that into the "indented" environment).

@jensmaurer: I thought raggedbottom is the default. What are we currently using?

@tkoeppe: There is no explicit \raggedbottom or \flushbottom in the source.
Maybe the key is this trick: \addtolength{\topskip}{0pt plus 20pt} which tells the middle-layer page layout algorithm that not entirely filling the page is ok. Claims are \raggedbottom alone doesn't help here, because it is consider too late in the process.

It appears we need to allow a bit of vertical stretching between paragraphs: \setlength{\parskip}{1ex plus 1pt} (the Latex default is "0pt plus 1pt", it seems).
It seems the only stretchable space we have is around headings, which is not enough to make Latex happy. Also, we need to nudge Latex into allowing more empty space at the bottom for \raggedbottom.