I have had good luck with fengrave (example Inlay for Kids Stool)
Can you share the settings you are using in fengrave (screen shot maybe) as well as the endmills you are using.
Are you using a z-probe when you change bits? (assuming you are cleaning with a flat bit and using an engraving bit for the profile)
One thing I have had luck with is setting the depth an extra .2 microns deep or so for the engrave to help the transition between the two cuts.