My understanding (and I previously have been the temporarily handicapped--I broke an ankle and was in cast + crutches, then using a cane when I got out of the cast and was rebuilding my muscle strength) is that those stalls are handicapped-accessible, but that they are not handicapped-exclusive, nor are they total "skip the line". Particularly in smaller bathrooms where there are only two stalls (the 'regular' and the handicapped), if there's any line at all I do not think that the handicapped stall needs stay empty *just in case*. When more than one person is present who needs the handicapped stall, the normal line rules apply amongst those who need the special stall.
In other words, one handicap does not trump another. Nor does a handicap equate to wait-free usage of a public restroom.
And I do think that sometimes the retro-fitted accessibility is something that shows a clear lack of understanding of what it's like to need this access. The worst one I ever saw wasn't a bathroom, it was a wheelchair ramp which had been built onto the end of a sidewalk. The only problem was that the entry door opened *outward* across the path of the wheelchair ramp, so that if you had to use the ramp, you would have to go past the door, get the door opened, and then reverse (and turn on a standard sidewalk to go from sideways relative to the entrance to being able to actually move into the store).