Found the problem. Short answer: My stupidity.
Long answer: I did have randomness just not in the network but in the data preparation step. After loading the data into array, I first shuffled it before splitting it in training and test data. The problem here is that each time the word-to-index mapping is different. Thus before loading the state, I initialized the model each time with a different word-to-index mapping.
I now used a shuffled dataset file and skip the shuffling during the data preparation step. Now all is consistent.