I have a side blast forge, shaped like a canal (trench?). The air opening is somewhat above the bottom. Obviously, heat an fire rises. So when a piece of coal is BELOW the opening level, it stops burning. Usually, the it's the smaller pieces that sink.

The result is that small bits of coal (about rice size) get accumulated in the forge, and fill it all. Air cant get through, and it's just bad.

I can sift and trash it, but it's a waste of good (and expensive) coal. Is there a way to avoid or handle this situation?

As has been said on here before, you can save it in a bucket with some water in it and when you have enough grab a handfull, squeeze out the water and now you cave a ball of coal that should coke up in the fire.

You could look into lowering the air pipe or raising the bottom of the side blast forge to see if that helps burn the coal more completely. 

Bituminous coal in water will almost float, where the ash, debris, etc will definitely sink. You can "clean" the coal that way. Give it a gently stir and remove the coal by hand or with a fine mesh net.Keep the fine coal wet and use it as a black mud to put on the fire, coke up, and burn. This can be cone with coal dust from the bottom of the coal bin. Dry coal dust can be used as a punch lubricant.

Actually, heated air rises. Heat itself moves by conduction (travelling through material), convection (being carried by a moving fluid), or radiation.

I suspect that the coal at the bottom of your forge isn't burning because it's too far below the air flow from your tuyere and isn't getting sufficient oxygen to sustain combustion.