Aux replaces à les. Here we have à tous les so we cannot use aux.
Without the tous we would indeed say aux coins de rue.
For your second question, de rue is a noun complement and whether or not it takes the plural mark depends on the meaning on the sentence. Here, coin de rue is indeed to be seen as a unit (one may argue that there are intersections but in this sentence, one corner belongs to one street) and rue stays singular.
More information and examples can be found here: