3rd dimensional movement may not come up very often but creatures are still limited to the usual movement rules.
If a power or ability says that the creature only teleports three squares than they can only teleport three squares, regardless of which direction they are moving. There is nothing in the rules that states a creature can teleport any distance vertically so I'm really not sure where your DM is pulling that from. And as per GMJoe's comment, being able to teleport any distance vertically could lead to some very game breaking situations.
The Rules Compendium does refer to using squares in terms of vertical height under the heading Movement in Three Dimensions (as well as other sources like climbing and flying as noted in the comments) and mentions how you determine the distance between different elevation levels :
Placing a small d6 or d4 next to a miniature or token is a good way to measure its distance above or below ground level. The number on the die shows how many squares the creature is above or below that level. [...] Determining the distance between two creatures above or below one another is straightfoward: first, count squares between the two creatures as if they were at the same elevation, then count the difference between their elevations. Use the higher of these two numbers. (pg.206)
It's also mentioned in the RC that a creature's space is actually a three-dimensional cube and, although it does only say a creature's space, it's not a big jump to say that unoccupied spaces are cubes as well. As seen on page 200:
A creature's space is the area, measured in squares, that the creature occupies on the battle grid. This area represents the three-dimensional space that [...] Despite the cubic shape of its space a creature is not actually a cube (unless it's a gelatinous cube).
Therefore, the (40 foot high) ledge would be eight squares high and a creature that could teleport three squares (or 15 feet) would not be able to make that distance from the ground.