A) Is the leading edge perpendicular to the edge?  
B) Have you been using the sheet cut feature assuming you will get a square cut?  
C) What is your loading procedure?  When loading I hold the media with one hand while finding "center" by putting tension on the leading edge.  
D) Do you have witness marks on platen to observe skew during a job?
I will bet you a box of your favorite donuts your media's leading edge is crooked.  After successive prints my wife couldn't figure out why the cutter ate a run of decals. She said: "But I use the sheet cut every time".  After removing the media I found her machine cut edge to be 9/16" out.  She would realign that cut edge to the dividing line between platens.  This created a stacking of tolerance issue.