How do I safely anonymize/hash a unique identifier to protect privacy?
Few answers to your questions 


Storing per address salt (assuming you are using it for encryption) is not same as storing the mapping with the hash. Salt could be public. 
You could encrypt anything with a public key for which there is no private key yet, Checkout more on Identity based encryption techniques.


Few additional inputs for anonymization


Any anonymization technique for the MAC Address (either encryption, hashing or tokenization) could be broken through inferential attacks based on rest of the parameters that are not anonymized. Since you intend to do traffic analysis, you would need to deterministically anonymize (retain the one-one mapping either through hash or deterministic encryption), any adversary who has access to same anonymized database can identify the same patterns! 
Other than inferential attacks on the logs/database, attacks based on implementation, key management, poor entropy etc also used in practice.
Micro anonymization techniques (say MAC addresses, IP Address and other field level anonymization alone ) are recommended only when any analytic s needs to be performed on the data, else it is better to encrypt the whole record.


Few references

*T. Farah, “Algorithms and tools for anonymization of the internet
traffic,” Ph.D. dissertation, SIMON FRASER UNIVERSITY, 2013

R. Pang, M. Allman, V. Paxson, and J. Lee, “The devil and packet trace
anonymization,” ACM SIGCOMM Computer Communication Review,
vol. 36, no. 1, pp. 29–38, 2006.

A. Narayanan and V. Shmatikov, “Robust de-anonymization of large
sparse datasets,” in Security and Privacy, 2008. SP 2008. IEEE Sym-
posium on. IEEE, 2008, pp. 111–125.*

Of course there are tonnes of other papers written on this topic over years.
You can read our recent paper published in IEEE- CCEM 2014 
http://www.researchgate.net/publication/265598254_Network_Telemetry_Anonymization_for_Cloud_Based_Security_Analysis_-Best_Practices