Hello.
It is not a direct bug of the Fuse operation. The issue with not valid edge orientation in Wire. You had bad connected shapes by BRepCheck_Analyzer. You can check the validity of your shape by check shape operation.
// Define the height of the box
double height = 1000.0;
// Create vertices
TopoDS_Vertex v1 = BRepBuilderAPI_MakeVertex(gp_Pnt(0, 0, 0));
TopoDS_Vertex v2 = BRepBuilderAPI_MakeVertex(gp_Pnt(500, 0, 0));
TopoDS_Vertex v3 = BRepBuilderAPI_MakeVertex(gp_Pnt(500, 100, 0));
TopoDS_Vertex v4 = BRepBuilderAPI_MakeVertex(gp_Pnt(0, 100, 0));
TopoDS_Vertex v5 = BRepBuilderAPI_MakeVertex(gp_Pnt(0, 0, height));
TopoDS_Vertex v6 = BRepBuilderAPI_MakeVertex(gp_Pnt(500, 0, height));
TopoDS_Vertex v7 = BRepBuilderAPI_MakeVertex(gp_Pnt(500, 100, height));
TopoDS_Vertex v8 = BRepBuilderAPI_MakeVertex(gp_Pnt(0, 100, height));
// Create edges, reusing vertices
TopoDS_Edge e1 = BRepBuilderAPI_MakeEdge(v1, v2);
TopoDS_Edge e2 = BRepBuilderAPI_MakeEdge(v2, v3);
TopoDS_Edge e3 = BRepBuilderAPI_MakeEdge(v3, v4);
TopoDS_Edge e4 = BRepBuilderAPI_MakeEdge(v4, v1);
TopoDS_Edge e5 = BRepBuilderAPI_MakeEdge(v5, v6);
TopoDS_Edge e6 = BRepBuilderAPI_MakeEdge(v6, v7);
TopoDS_Edge e7 = BRepBuilderAPI_MakeEdge(v7, v8);
TopoDS_Edge e8 = BRepBuilderAPI_MakeEdge(v8, v5);
TopoDS_Edge e9 = BRepBuilderAPI_MakeEdge(v1, v5);
TopoDS_Edge e10 = BRepBuilderAPI_MakeEdge(v2, v6);
TopoDS_Edge e11 = BRepBuilderAPI_MakeEdge(v3, v7);
TopoDS_Edge e12 = BRepBuilderAPI_MakeEdge(v4, v8);
// Create wires for bottom and top faces
TopoDS_Wire bottomWire = BRepBuilderAPI_MakeWire(e1, e2, e3, e4);
TopoDS_Wire topWire = BRepBuilderAPI_MakeWire(e5, e6, e7, e8);
// Create bottom and top faces
TopoDS_Face bottomFace = BRepBuilderAPI_MakeFace(bottomWire);
TopoDS_Face topFace = BRepBuilderAPI_MakeFace(topWire);
// Create side faces reusing edges and reversing orientation if necessary
TopoDS_Wire sideWire1 = BRepBuilderAPI_MakeWire(e1, TopoDS::Edge(e10.Reversed()), TopoDS::Edge(e5.Reversed()), e9);
TopoDS_Wire sideWire2 = BRepBuilderAPI_MakeWire(e2, TopoDS::Edge(e11.Reversed()), TopoDS::Edge(e6.Reversed()), e10);
TopoDS_Wire sideWire3 = BRepBuilderAPI_MakeWire(e3, TopoDS::Edge(e12.Reversed()), TopoDS::Edge(e7.Reversed()), e11);
TopoDS_Wire sideWire4 = BRepBuilderAPI_MakeWire(e4, TopoDS::Edge(e9.Reversed()), TopoDS::Edge(e8.Reversed()), e12);
TopoDS_Face sideFace1 = BRepBuilderAPI_MakeFace(sideWire1);
TopoDS_Face sideFace2 = BRepBuilderAPI_MakeFace(sideWire2);
TopoDS_Face sideFace3 = BRepBuilderAPI_MakeFace(sideWire3);
TopoDS_Face sideFace4 = BRepBuilderAPI_MakeFace(sideWire4);
// Create a shell and combine all faces
TopoDS_Shell shell;
BRep_Builder builder;
builder.MakeShell(shell);
builder.Add(shell, bottomFace.Reversed());
builder.Add(shell, topFace);
builder.Add(shell, sideFace1);
builder.Add(shell, sideFace2);
builder.Add(shell, sideFace3);
builder.Add(shell, sideFace4);
// Create a solid from the shell
TopoDS_Solid solid;
builder.MakeSolid(solid);
builder.Add(solid, shell);
Best regards, Commenter-1.