Yes, getting the feeds/speeds right is the key. I bought some inexpensive single flute carbide (straight) cutters and got decent results. I believe I slowed my router down to 10K RPM and was using cutting speeds of 60-90 IPM. Similar stepdown of .125" with a .250" diameter bit. With the slower RPMs, the tradeoff is you get more "scalloping" along the edges, but a lot less melting. You can always try and go back with a slower finishing pass and take a very light cut.
Another thing that helps is to run some compressed air at the bit to help keep things cool. If you can do it, a fine mist of water also helps out - but I run dry due to my MDF workboard.