The thread https://mathoverflow.net/questions/35468/widely-accepted-mathematical-results-that-were-later-shown-to-be-wrong contains combinatorial examples, e.g., the Perko pair in knot enumeration [<cite authors="Perko, Kenneth A. jun.">_Perko, Kenneth A. jun._, [**On the classification of knots**](http://dx.doi.org/10.2307/2040074), Proc. Am. Math. Soc. 45, 262-266 (1974). [ZBL0256.55004](https://zbmath.org/?q=an:0256.55004).</cite>], the classification of all convex pentagons that tile the plane [<cite authors="Kershner, R. B.">_Kershner, R. B._, [**On paving the plane**](http://dx.doi.org/10.2307/2314332), Am. Math. Mon. 75, 839-844 (1968). [ZBL0165.23801](https://zbmath.org/?q=an:0165.23801).</cite>], 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 [<cite authors="Grünbaum, Branko">_Grünbaum, Branko_, [**An enduring error**](http://dx.doi.org/10.4171/EM/120), Elem. Math. 64, No. 3, 89-101 (2009). [ZBL1176.52002](https://zbmath.org/?q=an:1176.52002)</cite>)]), 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 [<cite authors="Frolov, Michel">_Frolov, Michel_, [**Equalities of the second and third degree**](http://dx.doi.org/10.24033/bsmf.447), Bull. Soc. Math. Fr. 20, 69-84 (1892). [ZBL24.0176.01](https://zbmath.org/?q=an:24.0176.01).</cite>]. 

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. [<cite authors="Lam, Clement; Tonchev, Vladimir D.">_Lam, Clement; Tonchev, Vladimir D._, [**Classification of affine resolvable \(2\)-\((27,9,4)\) designs**](http://dx.doi.org/10.1016/S0378-3758(96)00018-3), J. Stat. Plann. Inference 56, No. 2, 187-202 (1996); corrigendum ibid. 86, 277-278 (2000). [ZBL0874.05009](https://zbmath.org/?q=an:0874.05009)]</cite> 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 its clear that not all examples above check 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 [<cite authors="Cormode, Graham; Jowhari, Hossein">_Cormode, Graham; Jowhari, Hossein_, [**Corrigendum to: “A second look at counting triangles in graph streams”**](http://dx.doi.org/10.1016/j.tcs.2016.06.036), Theor. Comput. Sci. 683, 31-32 (2017). [ZBL1370.68121](https://zbmath.org/?q=an:1370.68121).</cite>], where the algorithm needed a substantial correction which also led to a significantly modified result.