Most of our borders are 10mil. I've never thought about the absolute milling sizes - most tolerances are +/-5mil. I can only assume a boards temperature would affect some of that.
I have some experience with PCB milling, so I'll say a few words here.
If you use an outline layer to define the edges of your board, then the manufacturer will rout to the centreline of the border track. The software we use does this automatically (when I say 'we' I mean the company I work for, not SFE). The width of the track is not important. What IS important is that the border tracks meet each other accurately at the corners.
There are some issues I know of that affect routing accuracy. The major one is that the panels to be routed are aligned with the router machine using 0.125" inch pins. This is always likely to introduce some error. Sometimes, for example, the pin hole in the panel is damaged, or blocked with solder so that the pin doesn't insert properly.
The other issues are all related. The router bit does bite into the material and this can cause deflection due to the tool bending slightly, or wear on the router spindle, or even the material distorting slightly during routing. FR4 probably doesn't distort much, but perspex certainly does.
I've seen badly aligned edges due to the CNC router being incorrectly homed, but this is a hardware problem and not the common experience.