Latitude and longitude exist as boundaries outside the domain of map projections. A different projection may draw these lines or curves differently, but they still delineate the same geographic boundaries. E.g. a different projection may not show rectangles, but instead curved regions, but the cities existing in those regions would be the same.

If you are thinking of drawing arbitrary rectangles on arbitrary projections, then you'd have to come up with a rigorous way to define your rectangles. If you don't, then you're just drawing random shapes on other random shapes. Either way, yes, a different projection with the same rectangles drawn over it would yield different answers, and this should be immediately obvious.

Even the exact same projection but a slightly shifted 0° meridien would yield a completely different list of cities.