A Mil-Dot is 1/1000th of a dot. They're very hard to see. That's why only snipers can use mil-dot scopes because of their great eyesight.
There are two types of adjustable scopes to think about, first-focal-plane reticle and second-focal-plane reticle.
On a first-focal-plane scope, the reticle appears to change size as the magnification is changed. On these scopes, the distance between the mil-dots at a given range will be constant. At 100 yards, it should be 3.6" or whatever the manufacturer specifies as the subtension since there are several slightly different values for a miliradian depending on who you ask.
On a second-focal-plane scope, there will be one specific magnification level where the subtension matches the specification. On most scopes, it's the highest magnification level. I've got 3 mil-dot scopes, all 2nd focal plane, and all of them are correct at the right magnification.
You may need to be a little more specific in your question because if you have a scope where it's not the correct subtension at the specified magnification, the manufacturer should fix it for you.
Matt