Partisan bias in redistricting persists because there are strong incentives to do it, it is hard to define, and it is non-trivial to find solutions to.
The U.S. Constitution does not expressly forbid gerrymandering and vests redistricting largely within the authority of U.S. states once the census allocates the number of U.S. House seats to each state and gives states wide (but not unlimited) discretion in establishing districts.
Prior to the 1960s when Baker v. Carr and related U.S. Supreme Court cases established a firm one man, one vote rule that rendered unconstitutional state legislative districts with large disparities in population between districts in state constitutions with a house represented in a manner modeled on the U.S. Constitution's system for the U.S. Senate, county line based districts with large biases in favor of rural areas were common.
The case law created requirement that redistricting requirement that districts be contiguous has also been strictly enforced and uncontroversial.
At the U.S. House District level, federal statutes require that single member districts be used in redistricting and every state government has followed suit in its state legislative elections.
Constitutional redistricting case law calls for districts to also be compact and to reflect existing political boundaries and communities of interest when possible. But these requirements have not been enforced strictly.
The U.S. Supreme Court has been skeptical that simple partisan gerrymandering (i.e. drawing representative districts in a manner calculated to favor a political party) is improper when it isn't expressly racially discriminatory, in part, due to the U.S. Constitution's intentional refusal to give any formal role to political parties in the U.S. scheme of governance, something that almost all state constitutions in the U.S. concurred in doing.
Indeed, there is an argument that it is even contemplated, with the idea being that gerrymandering in one partisan direction in some places balancing out gerrymandering in the other partisan direction elsewhere.
There are multiple different definitions of gerrymandering. None has consensus support.
One measure quantifies the average compactness of districts in a map covering an entire state, which can address the worst cases, but is technical and doesn't squarely address the real perceived problem of bias in favor on one party and against another.
You can have two maps with similar levels of compactness, one of which strongly favors one party and the other of which strongly favors another party.
You can hurt a party, even with compact districts, by concentrating it supporters in as few districts as possible which are as pure in supporting that party as possible, in districts that party will win, while drawing districts in favor of the other party with enough support for that party to safely win, but with a large minority of members of the first party whose votes get cancelled out. There is a delicate balance between drawing competitive districts that leverage smaller percentages of the party with an edge in a district, and representing meaningful real world communities of interest (which lacks this leveraging benefits because a party has strong and pure support there).
The main problem is that any single member district system inherently exaggerates the legislative seat advantage caused by a percentage difference in voting support, especially to the extent that differences in voting support are not strongly correlated with geography.
In a single member district system, no matter how fairly the district boundaries are drawn, if the state homogeneously has 52% for the green party and 48% for the yellow party, the green party will win 100% of the seats in the legislature.
Usually, there are regional differences, but the less perfectly everyone in any geographic areas always favors one party or the other, the more any districting system, no matter how fair, will provide an outsized number of seats for the party with the most overall support, and will underrepresent a party with less support statewide, even if that support is significant.
All other things being equal, if one tries to draw a "fair" map without regard to the partisan mix of different parts of a state, single member district system is inherently biased in favor of Republicans over Democrats (relative to a proportional representation system) in the U.S. context.
Democrats are more geographically concentrated than Republicans (with very high percentages of Democrats in central cities with lots of people in them) and have far fewer areas where they have a safe majority in a geographic area that is leveraged by a significant minority of Republicans.
Republicans are similarly very geographically concentrated in very rural areas, but there aren't all that many people, Republican or otherwise, in rural areas.
Most Republicans live in suburbs or exurbs, many of which have a modest Republican majority that is leveraged by a significant minority of Democrats, and this is the situation that is favored by a single member district system.
If your state is urbanized enough, Democrats still come out ahead by sheer force of numbers, but they still tend to be underrepresented relative to the number of voters who are Democratic and vote, by a single member district system, unless one is really clever and aggressive in the way that you draw your district boundaries.
A Proportional Representation Baseline
One measure compares the overall support of legislative candidates of each party for the state as a whole to the number of seats in the legislature secured.
This is the most practical interpretation of what one means by gerrymandering - i.e. creating partisan bias in favor of one party relative to its share of voters by drawing district lines in a particular way.
But, as noted above, it is difficult or impossible to do so with single member contiguous districts, even if they are reasonably compact and often track existing political boundary-lines and communities of interest, unless the geographic distribution of members of a party in each state is just right (which is rarely the case).
This kind of test also offends the "party-blind" norm implicitly found in the U.S. Constitution and state constitutions that doesn't formally acknowledge that political parties exist or given them a formal role in the political process at the constitutional level.
One measure looks at partisan efficiency. This means how many votes in excess of what is needed to win a party wins in each district are present, which is then aggregated for the map as a whole.
This measure is probably the best one given the inevitable limitation of single member districts rather than proportional representation, because it isn't measured against the unattainable ideal of proportional representation results in a single member district system that intentionally exaggerates much smaller differences in voter support in terms of legislative seats.
Instead, this measure calls out an mathematically penalizes maps that unnecessarily concentrates members of a party in as few districts as possible to deny them leverage, while maximizing the leverage that the other party receives with safe but not monolithically one party districts. These tactics tend to bias the result against parties placed in concentrated districts, and by discouraging these tactics, this measure evaluates gerrymandering within the realm of the possible.
This measure has only been widely known and used for a short period of time although it is gaining popularity.
But, this kind of test also offends the "party-blind" norm implicitly found in the U.S. Constitution and state constitutions that doesn't formally acknowledge that political parties exist or given them a formal role in the political process at the constitutional level.
Also, this test puts to redistricting law values in conflict with each other.
In order to prevent racial discrimination in redistricting, the Voting Rights Act favors the creation of majority-minority districts that strongly tend to elect minority race legislators. But creating majority-minority voting districts also concentrates Democrats in fewer districts, depriving them of the maximal number of Democratic representatives in the legislature. Majority-minority districts give you more non-white legislators at the cost of fewer Democrats overall (the party that minorities for whom majority-minority districts are created in the U.S. overwhelmingly prefer).
A partisan efficiency measure of gerrymandering tends to disfavor majority-minority districts in favor of districts that provide Democrats with more leverage.
So, in conclusion, why is preventing gerrymandering hard?
There aren't good non-partisan ways of defining gerrymandering that really produce a fair result relative to a proportional representative ideal in most parts of the U.S., because of the way that supporters of the two major parties tend to be distributed geographically.
Constitutional norms aren't strongly offended by efforts to favor one political party over another because constitutions don't like to acknowledge that political parties exist.
Even if you are openly considering which political party is favored or not in a map (which is what most of the participants in the process actually care about), considerations of a fair partisan balance and racial diversity in legislative bodies compete with each other when one draws legislative seat districts, depriving someone trying to be fair of an "ideal" map option that can be unambiguously favored.
There is no consensus on the right way to quantify gerrymandering, even though some of the more extreme examples of it can be clear.
There is an under-appreciation among non-specialists in political science and in the relevant legal standards that redistricting is a global process and must be evaluated for the map as a whole, not on the basis of whether an individual district is or is not gerrymandered in a vacuum, even though emotionally, particular misshapen districts are attractive for judges and politicians to focus their attention on and these misshapen districts are what galvanized opposition to gerrymandering in the first place.
The arts of maximizing a party's support with a legislative map consistent with equal population contiguous districts is subtle and technical and is hard to easily articulate into a legal standard that can be easily applied.