The first sentence means that the queues start in London and reach as far as here. The second means that the town's history began before 1500 (and is still continuing today). The third means that the man's 'history' of violent crime began when he was very young (and is still continuing today). You could possibly omit the 'back' in the first example because we're talking about physical space, so the meaning of 'stretch' could be taken literally. It is better to include 'back' or 'as far (back) as', though. In the second and third, you can't. If you're talking about time, 'stretch back to' is a phrasal verb and has a purely figurative meaning. The 'back' part is essential, because 'stretch' on its own has no meaning here - it's a phrasal verb and you need both parts for it to be meaningful. Other phrasal verbs which have the same meaning and that you could use here are 'go back to' and 'date back to'.