Why was the shape of German states pre-WWII (especially Prussia) so complicated?

The shape of "all" European feudal states was as complicated as that of Prussia's as late as the fifteenth century, that is, up to 1400-1500. So the real question is why was Prussia's shape so complicated as late as the nineteenth century, that is four centuries after "everyone else."

The answer is that Germany, generally, and Prussia, particularly, was late in uniting. France was united after winning the 100 Years' War in 1453, Spain was (mostly) united after the marriage of Ferdinand and Isabella, and the victory over the Moors in 1492, the Netherlands won independence from Spain early in the 17th century, the United Kingdom (in its present form) came into being in the 18th century after the absorption of Scotland, and "pacification" of Ireland, etc. Germany did not unite until 1871, with Prussia leading the way, which is why some of the feudal divisions dating back to the Middle Ages were not erased until then.

Actually, "Prussia," consisted of numerous parts. The namesake eastern part was colonized by the Teutonic knights in the 13th century. It was acquired by Brandenburg, the area around Berlin (through marriage) in the 16th century. There were Rhineland territories that were added to Prussia early in the 18th century; not to mention Silesia and conquered Polish territories between 1740-1795. Each region (and many sub regions under them) had its own distinctive culture. It was only by a common "citizenship" that they were bound to the others, and were differentiated from non-"Prussian" Germans such as the Bavarians, or others.

I'll try and address your questions separately. Source is mostly personal experience; I used to live in the city-state of Bremen, as well as in the capital of former Prussia, Berlin. You also didn't mention which time period you are talking about; some things have changed dramatically over the centuries. Some things also were different in different parts of Germany, so a completely universal answer is not possible.

Also please keep in mind that even the concept of Germany is somewhat fuzzy and has shifted dramatically over the centuries.

Why was the division of territory within Germany so complex?

Others have already offered several explanations. An additional factor was that land ownership, on all levels, was largely hereditary. Territories were often split among children, and merged through marriages. This extended from the highest level of royalty down to the individual acreage of farms, and frequently caused very small fractured farm ownership.

This was not universal, though; there also was the opposite phenomenon: a father might want to keep the farm together and give it all his eldest son. This left the remaining children poor and without prospects, and was one of the main drivers behind emigration to the USA.

The other answer to your question is that, to some extent, the question really never arose. Keep in mind that the world in the era you are talking about was very different from today's world. Think about why you are even concerned about territorial integrity. Pretty much every reason I can come up is something that matters in today's world, but wouldn't have mattered in the 16th or 18th century.

People for the most part didn't really travel very far (in part because travel was slow and expensive, and in part because most of the land was wild and had no effective police force. Highway robbery was rampant). Territorial integrity beyond the next village held very little interest. Borders really only became a major impediment to economy and travel in the late 19th and early 20th century.

As a personal speculation, rather than part of your answer, having complicated borders may actually have been a benefit. As the saying goes "strong fences make good neighbors" and having an "international" border around your village might well make for a better fence than having just some township boundaries.

Yet another factor is simply time. Looking at Bavaria and Prussia, Bavaria has a much longer contiguous history; Prussia was mostly empty land until the 1700s.

Finally, the Lutheran reformation, followed by the counter-reformation, caused major territorial changes as individual towns or counties fell to the Lutherans, or went back to the Catholics.

Did people living in all those different parts of Prussia really identify themselves as Prussians? Even if someone from the two neighbor villages would be from two other Länder, and someone from a very remote land would also be a Prussian?

For the most part, the various states were more political entities than cultural ones. The idea of identifying with your country only started gaining traction with the rise of nation-states, starting with the American and French Revolutions.

Culturally (and legally), people would usually identify mostly with their city, or the castle, or at best with their general region. Our English word "citizen" is derived from "city" and the German translation of citizen, "Buerger," refers to "Burg" (castle). A Buerger was somebody who was allowed to live in the village immediately surrounding a castle, and enjoy protection from the lord.

Culturally, this idea still survives even today. I used to live in the city-states of Bremen, and it really didn't matter if you were a German citizen; you were considered a "foreigner" or at least not a local unless your grandparents were born there. Some other cities had more generous rules; in some, it was enough to live there for one year and one day to be considered a local.

Same question for other enclaves, e.g. did people from southern Palatinate identify themselves as Bavarians?

Sorry, I don't know the answer to that. My experience is more with Prussia.

Since Prussia was pretty much doing what it wanted in Germany, why didn't Prussia just take over those tiny states that are entirely encapsulated within it, to simply cover the entire north Germany?

It was really not important for Prussia. Prussia had a big problem: too much land and not enough people. Trying to consolidate territory would require either extensive negotiations, or spending resources on a war. You'd need a good reason to do it, not just "because it would look better on a map". Even more so when there was no threat from these tiny states. Why would Prussia want to do that when they are really just more mouths to feed when they didn't have enough farmers to produce food?

Also, several of these tiny states were very important economically as trade hubs (in particular, the Hanseatic cities). So while Prussia was generally hurting for people, they didn't necessarily want to encourage people from those cities to move to Prussia. Prussia did actively recruit people from other parts of Germany, and famously declared religious freedom in order to attract French Hugenots after the revolution.

There are actually interesting topics and bits of trivia about this lack of people, but they would be too far off topic for an answer to your question.

Why was this changed after WWII, and, why wasn't this changed after WWI?

These things weren't "changed" deliberately. Rather, historical events caused new borders to be drawn with little regard to existing borders. It just happened that many of the former enclaves and exclaves were "paved over" (many still survived, though). WW II simply was particularly catastrophic in that respect.

Also, for the most part, the borders really weren't cleaned up, they often continue to exist but just became less relevant. Enclaves and exclaves and all kinds of other illogical boundaries still persist to this day (for instance, the state of Bremen consists of two cities, Bremen and Bremerhaven, with no contiguous land between them; they are separated by Lower Saxony territory. Enclaves and exclaves also abound along the border with Austria and Switzerland)

The first push for territorial integrity actually was in the 19th century; the revolution of 1848 was a push for uniting Germany as one nation. That revolution pretty much failed, but did lead to the formation of the Second German Empire in 1870. The outside borders of that empire were comparatively clean.

WW I did not cause too much internal territorial changes simply because Germany continued to exist as a nation. Of course, Germany did lose some territory along its borders.

The reason WW II made more dramatic internal changes came about because Germany as a nation was divided up; one could almost argue that it ceased to exist and was re-created from scratch. That had many consequences.

The most obvious one is that the major cultural divide in Germany used to be between North and South. After WW II, the major cultural divide was between East and West.

Another consequence is that many of today's state lines reflect lines of allied occupation. The most obvious example is the line between the 5 Eastern states and the 11 original German states, as well as the western border between Berlin and Brandenburg (even the fact that Berlin is a separate state is due to the Allied occupation). The border between Germany and Poland is similarly shaped by Allied forces and has no historical background whatsoever.

Another example is, again, the cities of Bremen and Bremerhaven. The reason they are still a city-state is that Britain occupied most of northern Germany, while America occupied southern Germany. That did not give America a sea port. Thus, Bremen/Bremerhaven was American-occupied territory, rather than becoming incorporated into the surrounding British Lower Saxony.