As mentioned above, and on the Map counties page, the borders you see on the map there are simplified. What this means is that they might be built upon a thousand points instead of a million. This is to make it more usable and faster in the web browsers. Ultimately we would use better polygons when zoomed in, but we don't.
When calculating where the geocaches belong, we however use the best data we can and have access to. For most countries, this is data from Openstreetmap. The data is not extracted live or automatically, so quite often we might have over a year old data. Borders normally don't change, but sometimes Openstreetmap changes their data to the better.
I took a closer look at http://coord.info/GC4DHFY since you mentioned it specifically (which is great). I will attach a screenshot from Openstreetmap, where I have added a marker at the coordinates of the geocache.
(right click the image and open in new tab to see it in full size)
As you can see, the marker is on the west side of the border in the river, according to OSM, our source. Now I didn't look up which county is which, and I don't know German geographics down to that detail on the top of my head (I am from Sweden...). But you mentioned that you thought it belonged to the eastern county, so I assume this disproves the case.
Then as mentioned in the comments. 100% correct borders are very rare. I am not saying OSM is correct. But it's likely that Google maps is much much worse with their borders, they usually are.
I hope this answers your question. If you want to check other geocaches, visit openstreetmap.org and paste the coordinates as a location to see where the marker ends up. If it's correct there, and wrong at Project-GC, we will look into it, maybe we have to update our German polygon data then.
As a side note. For Sweden we do not use Government data since it's not free. We use data from a statistical entity since it seems to be the one that's closest to reality, of the free ones. Lantmäteriet who owns the data in Sweden is changing their policy in 2016, we will see what happens with Swedish polygon data that year.