That's how Apple's shuffle works (it's the same on iPods). When you press shuffle, a random order of songs is created, but from there on, it acts like a regular playlist. You can move back and forward as much as you want, manually select songs, doesn't matter - it will stay exactly like it was shuffled the moment you turned shuffle on.
If you want to change the order, you don't need to restart iTunes, you can turn shuffle off and back on - this will simply mix it one more time, but that's all you can do. You can't make it completely random.