Some Lower Bounds Related to the Missing String Problem