"Select Interior Faces" buggy and unpredictable?
First, it may be useful examine this in wireframe display, instead of the solid display you have in the screenshot in your question. I suspect the reason why some of what are marked interior might be more obvious that way. 

Whether the problem is a bug, will depend in part upon how one defines what a bug is. I suspect that in this case, the software is working as designed, and the problem lies in the difficulty in describing for the software what an constitutes an "interior face". The best definition of "interior faces" I can find is in the hint that appears if you hover the cursor over the "interior faces" option of the select menu in the 3D viewport in edit mode. That reads


  Select faces where all edges have more than 2 face users.


which explains why some faces that appear to be exterior faces are selected in your screenshot. For example in the center of your screenshot are three exposed faces which are showing to be as "interior" Examining these closely, you will see that each of the edges of these faces is connected to three different faces. For example, the leftmost edge of the left face is connected to the two fades one can see on either side, and then also connected two the face perpendicular to these two. Examining the other three edges would reveal that each edge is part of three faces, and by the definition of an inside edge as given in the tool tip, the face is interior.

There are also classes of interior faces that the algorithm would not catch. An example of one of these is an interior face in a cube defined by the lower far left, the upper far right, and upper near left vertices. When displayed solid, it is obvious that this is an interior face, but none of the edges belong to more than one face, so it would not be reported by the "select > Interior faces" option.

I don't know that I'd say the algorithm is poorly implemented, but it might be that this may be a good implementation of an algorithm that is not the best one for your purposes. 

You might find the algorithm associated with the "Non-manifold" option from the select menu item (shortcut SHFT-CTRL-ALT-M to give more satisfactory results, although I don't know how this algorithm is different from the "interior faces" one.

You might also reconsider how your tool that generates the python script, is generating a new cube? The screenshot suggests that you may be generating the new cube by adding a new cube mesh primitive. If this is so, it might result in the kind of interior faces you are seeing in the screenshot. As an option, you might modify your python script so that where you need a new cube, check to see if will be attached to the existing mesh. If it is, then check to see if there is a common face between the new cube primitive and the existing mesh. If there are no common faces, check for common edges between the new cube primitive, and the existing mesh. And if there are neither any common faces, nor common edges, check for common vertices. If there are common vertices, edges, or faces, then create the needed geometry by extrusion from the existing mesh, rather than adding new primitives, because extrusion should reduce the number of interior faces. Of course, if you need a cube where you don't have an element to extrude from, then you'll have to add a mesh.