> If you clear your Google history (as you should), can they still respond to an order like this with your name?

Assuming they still have the data (didn’t delete it, just “cleared” it), then yes.