Merchant Category Codes are assigned by acquirers, not by the merchants or card issuers. I doubt that anyone at the store level would understand the question or have access to authoritative information.
Department stores are VISA Merchant Category Code 5311.
Go to this site:
http://visa.via.infonow.net/locator/...tLoadAction.do
...set the MCC Search Type to Numerical, choose 5311, and you should be able to find qualifying merchants. No guarantees that American Express, MasterCard, or Discover categories will be identical.