I'm just guessing here, take it all with a grain of salt. I
think that that the algorithm that syncs the NXT motors might only work if you leave the speed beneath 100% because it will speed up the motor that is slow, meaning that if you try to sync two motors at 100% speed, it can't speed up the slow motor which makes it curve. When you leave the target speed lower, it leaves a bit of "headroom" for the NXT to use to sync the motors. Now, if the NXT would see when the speed was set at 100% and instead of trying to speed up the slow motor, slow down the fast one, you might get a straight line. Remember, this is just an uneducated guess.
If you do want slightly better results, use the method Techbricks.com
suggested, picking the two motors that perform the closest. I hope you get something working!
-EDIT- Oh and if the problem of having the motors start slightly out of sync becomes an issue, have the motors first start at a lower speed like 5-10% and then ramp up to what you want them at. This might help as then the amount that one motor turns before the other starts up will be less. However, if they don't quite get the speed setting updated at the same time, you'll have the same problem all over again. Just something to think about.