I use a dish brush to clean colanders and other kitchen items that have holes in them (like some cooking spoons). While sponges get torn apart if you scrub them over the mesh of the sieve, the bristles of a dish brush do not have that problem. The bristles also move independently of each other, and can find their way into the tiny holes in the mesh.
I recommend using the same technique dentists recommend for tooth-brushing: apply some pressure of the bristles against the mesh and then move in small circles. This allows the bristles to dig into holes of the mesh, rather than just dragging across the surface of the mesh. Also, you should clean both the inside and the outside of the sieve. (The suds from the dish soap will appear to penetrate from the inside to the outside, making the other surface look cleaned, but scrubbing with the brush is the way to remove stuck-on pasta and starch.)