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.)
I suggest flipping the sieve over and running water through it to make anything trapped in it fall into the sink. Spray anywhere there are visible particles, and flip it back over to inspect it for any remaining objects. This can take between ten seconds to a minute, depending on how dirty it is. I have used this method to clean sieves used to collect coffee grinds, and it is very effective. If you have a spraying attachment on your sink, set that to the highest pressure setting. You can also run it through the dishwasher to get any remaining starch off.
Fill a kitchen sink with enough (warm, soapy) water to submerge the sieve (or just the starchy part, if the sieve is big). Leave it to soak for 20 minutes (longer if the residue is really old and layered on). (You can soak other dishes at the same time as long as they are not greasy.) Rub with a sponge, or paper towel, or brush, or even your bare hands. The starch will come off. Then rinse under running water to remove soap.
(not exactly what you asked for) I think you can do yourself a favor by using a coarser sieve (if you have one). Searches "pasta sieve" on your favorite internet image search engine will probably yield sieves similar to this. Starch will not as easily get stuck in the wholes and the sponge enters the wholes better when brushing over.
The downside of those pasta sieves with slits is that with fine noodles like spaghetti, a few will slip through.