First, if it “only” cost $30M to store all audio for a year - that’s less than ten cents for each person in the USA. I assume the OP is asking about metadata, i.e. phone number to and from. That would be a trivial cost. But… storing audio would be a massive intrusion. The question about metadata is - why store it? One would think that after about, say, two years - 99% of any legal questions about phone use would have been asked and the records provided. What reason would there be?
As for spammers - the problem is, for uses like Skype and other VoIP services, there are gateways from the internet to the POTS (Plain Old Telephone Service) system. Like how email was never designed to prevent SPAM, the phone system was not designed to filter out illicit traffic. In the days where the design of digital switching was originally set, the assumption was interconnect was a very high bar open only to select companies. Today, phone to internet connections allow anyone to pretend to be a specific caller, and the receiving phone system does (or used to) accept any incoming call and attached caller ID data with little or no checking. Some programs I think used to let you compose any caller ID you wanted for your internet-originated call. Changing this technology would I assume be incredibly expensive and need international agreements to sort out.