Mild steel is a bit "gummy" unless you use a leaded variety.
You could use interpolated milling rather than drilling for holes of limited depth?
Have you tried single flute cutters? I know it sounds mad but they are easy to sharpen and I use them on some difficult stainless steel and carbon steel jobs.
Are you using flood coolant?

- Nick