This sounds oddly similar to my issue. See my findings here: Not cutting certain designs - #4 by seanchu88
TL;DR: Auto-Focus laser lens had accumulated smoke/dust INSIDE of the lens which could not be cleaned out directly. Using manual material height resolved the issue. Also using compressed air got a majority of the dust out but not the smoke residue so I can still using Auto-Focus but not reliably.