The thread Widely accepted mathematical results that were later shown to be wrong? contains combinatorial examples, e.g., the Perko pair in knot enumeration [Perko, Kenneth A. jun., On the classification of knots, Proc. Am. Math. Soc. 45, 262-266 (1974). ZBL0256.55004.], the classification of all convex pentagons that tile the plane [Kershner, R. B., On paving the plane, Am. Math. Mon. 75, 839-844 (1968). ZBL0165.23801.], the number of knight's tours, the number of of collections of 12 lines and 12 points, each incident with three of the others, the enumeration of 4-dimensional simple polytopes with eight facets, the number of uniform tilings of three-dimensional space (the latter three, and more examples, are given in [Grünbaum, Branko, An enduring error, Elem. Math. 64, No. 3, 89-101 (2009). ZBL1176.52002)]), Frolov's wrong claim that there is no series of 7 distinct odd numbers, from 1 to 49, with sum 175 and sum of squares 5775 he used proving the non-existence of 7th-order bimagic squares [Frolov, Michel, Equalities of the second and third degree, Bull. Soc. Math. Fr. 20, 69-84 (1892). ZBL24.0176.01.].
More examples might be found by checking published errata/corrigenda/retractions in the field https://zbmath.org/?q=so%3A+%28+corrigend*+%7C+errat%7C+retract*+%29+cc%3A*05, though most are likely not due to computational errors. E.g. [Lam, Clement; Tonchev, Vladimir D., Classification of affine resolvable (2)-((27,9,4)) designs, J. Stat. Plann. Inference 56, No. 2, 187-202 (1996); corrigendum ibid. 86, 277-278 (2000). ZBL0874.05009] contained a wrong table with design computations, as explained in https://doi.org/10.1016/S0378-3758(99)00055-5.
P.S. Just saw that the question has been modified inbetween; now it's clear that not all examples above satisfy all given criteria.
In fact, if we look into the set of combinatorial papers with corrections/retractions/errata/corrigenda that involve software https://zbmath.org/?q=so%3A+%28+corrigend*+%7C+correct*+errat%7C+retract*+%29+cc%3A05+sw%3A*, we obtain only 16 results, most of which have non-computational corrections. This supports the impression that these cases are relatively rare. The only example that may fulfill all criteria among them seems to be [Cormode, Graham; Jowhari, Hossein, Corrigendum to: “A second look at counting triangles in graph streams”, Theor. Comput. Sci. 683, 31-32 (2017). ZBL1370.68121.], where the algorithm needed a substantial correction which also led to a significantly modified result.
