How could they have prevented this? (Is this calling for a technical solution or is it a question of people and best practices?)
First things first, the ambiguity could possibly have been avoided with a better model. A rectangle can be represented as a pair (x, y) (or (top, left) to further reduce the ambiguity), a width and a height.
If one sticks with the structure where a rectangle has a top and a bottom, there is still no need for contracts here. You can easily guarantee that top < bottom (or the other way around) by using exceptions or assertions within the class. In other words:
Don't let anyone access class internals. getBottom and setBottom is OK (or if your language has properties, it's even better). Having a public field bottom is wrong.
This is why, for instance, C#'s guidelines forbid public fields: if you want to expose a value to other classes, use a property.
Make sure setBottom have specific controls which don't let bad data go in. If bad data tries to go in, throwing an exception is an appropriate reaction.
Note that you might have to handle a case where top and bottom are changed one after another; for instance, a rectangle with top: 3, bottom: 7 is moved ten points to the bottom; setting top to 3+10 would throw an exception, because 13 > 7. Depending on the usage of the class, you may have a shiftBy(x, y) method or something similar.
The rule such as top < bottom is an ordinary business rule. In the same way, a class Product should encompass a rule telling that the price cannot be zero or negative (unless in a specific domain, zero or negative prices make sense), and a class Temperature should have a rule that tells that values inferior to −273.15°C are not allowed.
All those rules belong to the classes themselves. This also means that if the rule should be changed later, you have only one location where you need to change it—the class.
Talking about contracts, they are not limited to CS classes. For instance, .NET ecosystem makes it not only possible to declare code contracts (including invariants) very easily, but also contains very powerful tools for static checking of contracts.
Some other languages, such as Eiffel, do have contracts as well, and the entire list of languages is quite impressive.
The benefit of the contracts, like they are implemented in .NET, is their propagation. If you're initializing a temperature class with a value of −300°C, you won't have to wait until runtime to get an exception: you get a error during the static checking (which, in some cases, means getting it nearly immediately in your IDE as you type the invalid value).
While convenient, you don't need it in order to avoid the situation you're describing. A simple exception/assertion would be enough.
What would be the best steps to fix the codebase, so that top > bottom always, and the myriad places where rectangles are emitted and consumed don't break?
That's a hard one. I'm surprised you haven't found the issue earlier (well, maybe not that surprised). I would expect the code start crashing from time to time because of the mismatch. For instance, if the code which computes an area of a rectangle assumes that top < bottom and if it's fed with a rectangle where top > bottom, the caller may cause an exception to be thrown when receiving a negative area while expecting it to be strictly positive.
Anyway:
If one part of the application assumes that top < bottom, and the other part does the inverse, and both don't interact, you can either keep it this way (while adding appropriate exceptions, assertions or code contracts), or just switch one of the parts to use the other convention (which may be quite difficult in practice).
Otherwise, put the exceptions in place and run the tests (if you don't have tests, good luck). If tests are correctly done, they will show you most of the occurrences of the mismatches. Of course, mismatches can also happen at the level of the interfaces between components, which won't be detected by unit tests. Checking manually your interfaces and adding exceptions there could be helpful (and make your interfaces less ambiguous).
Another technique which is worth trying is to create a new rectangle representation with a position, a width and a height. Once done, you can migrate code step by step to the new representation, while making sure to understand whether you should use a top or a bottom for the position. This way, you don't break existent code and don't slow down the team during the migration. Once done, the old rectangle structure can be removed.
