I don't see how the division treats vertices differently. All vertices are multiplied by the matrix, and all vertices have their components normalized by their W-component. The fact that the perspective happens to have a non-linear transformation changes nothing; the non-linear transformation is the same for all vertices, and if you have a projection matrix without perspective, then the non-linear function simplifies to a linear function.
The transformation is just a function y=f(x), where x and y are vectors and f is the transforming function. Without perspective, the function is linear and can be implemented as a matrix multiplication. With perspective, the function is non-linear because it requires a division, and thus cannot be implemented as a pure matrix multiplication. But in the end, the function f is the same for all vertices.