gr5: I did this in my game, http://imaginary-spaces.com. I generate all the geometry in my code, but it's a bunch of separate objects -- there's windows, stairs, walls, floor, all of them procedurally generated. The normals are correct in all the other software packages I've used (unity, meshmixer, meshlab, blender, ...), so I'm surprised you think they're backwards for Cura -- how do you see that? Also, the picture frame doesn't matter; I took it out and got exactly the same behaviour.
Daid, cool! But that seems to point to a bug: in the cube example, if you remove the four triangles in the middle, you'd get a long rectangular prism with normals all pointing out, and life should be good. So there's apparently some bit of logic that gets confused.
Following this lead, I loaded up this-file-busts-cura (apologies to Guthrie) in blender and removed one of the overlapping quads between the wall and the first window clockwise from the stairs. That let that window print correctly. Other parts were still wrong (unsurprisingly), and the weird gash showed up elsewhere.
Now I'm looking for free software that can post-process an STL file and fix polygons that point opposite each other... anybody hear of some?