A newspaper in Indiana pulled a similar stunt about a year and a half ago. They even published the database on the internet.
Don't write.
CALL.
Flood their phone lines.
Demand to speak to
1)The head of advertising, telling him you will not buy from any companies that advertise in the paper, and that you plan to call them and tell them why.
2)The editor, and inquire as to why he/she sees fit to infringe upon your right to privacy. Then make it abundantly clear that if your home is robbed and your guns are stolen that your lawyer will be talking to him.
In the case of the paper in Indiana, the database was only available on the web for a couple of days before it was taken down.