Two Worlds II

Foreword
I have spent countless hours scouring the internet for Two Worlds II maps where the locations of the caves are marked. Unfortunately, most of the results led to a German map on a dead site, so I decided to mark them myself as I progressed through the game.

My solution
In the first Two Worlds, once you found a cave, you simply had to enter it to start exploring. Regretfully, this system has been changed somewhat in the sequel, with the addition of red or simple locks to the entrance doors. The latter can be opened by plain lockpicking techniques, while the former either means that it requires a quest (which you haven't picked up yet) or that it will only be accessible in a later chapter. Because of these factors, I always checked and completed (where possible) available guild sidequests in every town that I entered, before proceeding with the main storyline.
In short, always check for new sidequests from guilds before progressing in the story. If there aren't any, simply continue to the next chapter then try again.

Other sources
If you haven't been able to locate all of the caves in a single walkthrough of the main game, don't fret, because you will still have a chance to unlock them (in theory) in the DLC (Pirates of the Flying Fortress).

Antaloor Map Guide
The red dots mark the caves that are also included in the collector's edition, whereas the blue dots are not. The red dots that are connected by a line are counted as a single cave by the game. This is because they have multiple entrances but ultimately still lead to the same place. It is important to know that you should only explore the cave marked by a yellow dot if you wish to finish the game, because once you enter it, you have no choice but to complete the main quest.
Note that these aren't all of the caves that are in the game, just the ones that I managed to find, but locating them will definitely net you the achievement!

Conclusion
If you have found my map and solution useful, please reward it with a positive feedback! Also, feel free to send me your ideas and suggestions.

To download the hi-res version of this map, right click on the image and select "Save as..." or click HERE.
(Last update: 2012.08.27)

Alright, here is my addition to the TOP solution to better help people out.

First, I want to say that I was 11/25 when I reached the end of Chapter 2 (I hadn't completed the last part to advance to chapter 3 though). But I had done EVERY quest from the mages, neco's, warriors and thieves! I had done a bit of searching and a few random quests, but not too much. So if you are here, and have done like I have, don't worry too much.

From here I followed the map that is post in the above solution. I had NOT explored the EAST of the first place you teleport into after your Orge base. So I followed that map to all the red and blue places and almost EVERY red and blue spot on the EAST and SOUTH of the first island gave me a dungeon.

But this didn't do it for me. I still was only at 22. I did find a quest back at the base that I had to do for the orge wizard which gave me access to a blue dot in the middle north of the first island (it will be locked until this is done).

Now I was at 23. Chapter 3 there is one dungeon and ONLY accessible if you don't kill the Witch (from what I understand). Side with her.

After that, I went to complete the game thinking 24 was good as I would have one more - SINCE the solution above posted said so.... NOT!

I finished the game with only 24.

I know there was at least one more quest from the Ogres that I missed, MAKE SURE YOU always go back during your advancing through the chapters and check there for quests as well. And there were 3 locks BLUE dots on the map when I was playing, which I am assuming were for quests.

Beware that the TOMBS (there are many of them) DON"T COUNT FOR THIS.

NOW - the good part. And this how I finally got it. The DLC for this game has... wait for it...6 dungeons!!!!!!!!!!!! Yes, I played it and did most of the quests with all the achievements and got up to 30 dungeons.

Not every dungeon counts. Just accept it. But perhaps if you just keep returning to the Ogre's main base you will get more quests and not need the DLC. But if you are going to get the DLC you can finish the campaign with 19 and still get the achievement AS LONG AS YOU GO FOR EVERY ACHIEVEMENT ON THE DLC IN ONE PLAYTHROUGH!!!!