iTunes doesn't really play randomly, it just changes the oder of your songs. Unless they changed it in version 4, it will play the same order every time. To solve, start it on a track that it never plays. It should follow to another track never played, and so on.
Dan