The story goes that they started building from two ends and when they met in the middle they found out the sizes didn't match, and that's why the had (have?) to load cargo between trains.
I've been using this factoid for a really long time, but i can't find any evidence for it. Wikipedia doesn't mention it and i didn't have any luck on Snopes. Am I thinking of the wrong railway or isn't there any truth in it at all?
No, contemporary sources make it clear that the usual Russian gauge of 5 feet was used. See, for example, The Living Age, Volume 223 Page 108 (1899). Here
The Chinese Eastern Railway, a shortcut across Manchuria to Vladivostok, was regauged to standard gauge during the time (beginning in the 1930s) when it was under Japanese control.
Ireland had a problem of this type. The first three railways all had different gauges, and in particular there was no single gauge between Dublin and Belfast. Eventually all three of them were re-gauged to 5'3" by Parliamentary Act. This left various narrow gauge railways, and one rather odder system using 0-3-0 locomotives (verbum sapientes).