"¿Quién comió mi sándwich de queso?"
Translation:Who ate my cheese sandwich?
I've never used cheese to eat anything. (Sorry, I couldn't help myself).
I guess a cheese sandwich could be called a sandwich with cheese, but it would be very uncommon to hear in my part of the world (Australia).
Also, your sentence, Who ate my sandwich with cheese is ambiguous, which is what prompted my quip at the beginning of this comment, this is why I would never advocate for it to be considered correct.