The question is difficult to answer for two different reasons:
1) Generally speaking there is the question what you consider the cache placed furthest to a geographical extreme in a given area. Should the header co-ordinates count or where the physical container is placed (in the case of multis, unknown caches, wherigos etc.)? For me it is clear that what counts are the header co-ordinates, because you cannot know where the final of any non traditional cache lies until you have found it / solved the riddle. Consequently, there is no way of telling which is e.g. the southernmost physical cache container in any given area. Generally speaking, PGC does exactly this when calculating geographical statistics, i.e. what counts are the header co-ordinates. However, geotrophy.net e.g. seems to use physical containers for their extreme points, so there does not seem to be a universal consensus on what definition to apply.
Remark: The downside of using header co-ordinates is that in principle COs could put the header co-ordinates of e.g. a mystery cache outside the geographical extreme point of a country into the sea (where this applies) just to own the geographically most extreme cache while there might be a pre-existing traditional which so far had been considered as being the most extreme one. While there is nothing in the rules preventing this, I would not consider this to be very fair.
2) What the southernmost cache in Europe is depends of course also on how you define Europe. Geographically? Politically? Unfortunately, geocaching.com and consequently also PGC are inconsistent in this respect. Some European countries (still) own territories outside Europe which geographically clearly do not belong to Europe. However, some of these territories are considered "countries" of their own by geocaching.com and PGC (e.g. Guadeloupe, Falkland Islands), others are not (e.g. Canary Islands). Consequently, it is impossible to use simple search functions on PGC to search for the southernmost cache of Europe.
Remark: an additional difficulty (even if marginal) stems from the fact that strangely enough PGC uses geographical data when determining the state and county a cache is in (i.e. levels 2 and 3 of geographical classification) but blindly trusts the CO when it comes to the country (i.e. level 1). Thus, when searching e.g. for caches in Spain you might get also a cache located in Ghana only because the CO decided to indicate the cache is in Spain.
Conclusion: As any politcal definition does not seem to make much sense when looking for the southernmost cache of Europe, I personally would use a geographical definition and look around manually. Which leads to GC2C49R "Trypiti - The Southernmost of Europe" on Gavdos as being the southernmost cache in Europe.
Hope this helps, and enjoy your trip to southern Greece :-)
