I happen to have a very good way of finding these, simply explore a stronghold that you find and 9/10 times it has an abandoned mine shaft running through one! It really works, and you can even prove it if needed. Example: on the seed "gimmeapoo" (this spawns you near an npc village that is in a shallow lake!) you will find abandoned mineshafts intersecting a stronghold at this location (-379, 27, 786). Be forewarned, very early on you may find random spiders (the regular kind) in the shaft. This is due to a dungeon that generated above the mineshaft, but at the end of a more different one.
In short, stronghold = mine shaft.
also, in the example mentioned above, there is a dirt room at (-437, 21, 854)