Should I always start from the same start state in reinforcement learning?
It depends on the task the agent is trying to learn and of course on the environment constrains. 

In an Atari game agents have a pre-fixed starting point because that's part of the games rules, so I would say that this is enough of a justification to make each simulation start from that starting point. Moreover, you have to pay attention to the kind of reward function you're using, for example (a really dumb one just to give a grasp of the concept) if you're rewarding the agent depending on how close it gets to the ending point rather than how far it goes from the starting point, the agent might end up having huge rewards only because it respawned close to end point, which would be an artefact and not a fair reward for a good action choice. 
Other situations in which it does not really make sense to select a random starting point might be dialogue systems, in which you know that a conversation start with greetings, therefore it would not be logical to make an agent starting with a random question or sentence (the space in these case would be made of different dialogue acts). 

There are anyway situations in which the environment allows a random selection of the start location of the agent. In this paper for example, an agent was trained to escape from a maze, and both, the exit point and the initial location of the agent where randomly selected at each iteration. This was partially due to research reasons, the authors were analysing the possibility to train policies more complex than a simple 'space memorisation' one but anyway, conceptually there's nothing wrong in this situation in selecting a random starting point. Other tasks could be following or escaping from a specific object, again, as long as the reward function is properly designed, even with a random starting location at the end the agent would anyway learn to move faster when close to the target (toward or in the opposite direction depending on the task). Actually, in this situation I think that a random initial location would have potential benefits, like avoiding the agents to learn biases due to external biases of the environment (like parts of space with less random obstacles than others).