In my two-column layout, if I don’t allow unbalanced columns, there are a number of pages with fairly significant space at the bottom - where it seems like it should be able to fill better. But I chose to allow a difference in columns of 1 line, and that seems to generally fill the pages better. But we still have weird problems like this 2-page spread:
The first column is 2 lines short of full, the second column is 3 lines short of full, and then there are two lines at the top of the next page, right before a new chapter heading. If those two lines had just slipped to the previous column, there would still be only one line difference between the columns, and the chapter could have started at the top of the page. (I don’t know how far ahead it looks, but the next page or two look like they could have handled the adjustment).
Another thing I see pretty often… one column is one line short, but the following line could have been shifted there without creating a widow, like this:
As you can see, the paragraph breaks aren’t near the page edges, so you could have easily shifted one line forward in each of columns 2-4.
I realize that there is a lot happening with XeTeX, and a lot of complicated calculations, and weighing goodness and badness and all, but some of these problems don’t seem to be very complex, to confuse the system like that…
Regarding your first example. TeX has broken the page at that position because to fill the left page, it would need to pull 2 lines across from the second column, which would also need 3 lines (for a total of 5 lines) from the next page. But 5 lines means you would pull the end of the paragraph, the heading and just 1 line from the next paragraph. This violates good Christian typesetting and would leave a widow. OK, so could we pull just one line across to balance the right column with the left? No, because again you would leave an orphan.
The way to fill up the page would be to reduce say the first paragraph on the page by 1 line, thus requiring 6 to fill and that would work (although a 2 line start of a chapter at the end of a page is not ideal).
Your second example is trickier and has me stumped. Do you have Advanced/Use glyph metrics turned on? If so, then your bottom margin may be a smidgen too high and a y descender is enough to not fit (but I’m straw clutching here). If you really want to know, you can turn on \tracing{o} and it will give you the whole story of how it went about balancing that page, but it still won’t tell you why TeX wouldn’t allow a certain split, just that it wouldn’t.
Another option: are you using font linking for your guillemots and if so is the ascender, or more importantly descender, of that font (e.g. Charis) much greater than the main body font. That could cause it to not want to pull the line from p1 col2 to col1. I’ll make that my guess and let you shout me down 
