I assume someone at Google reviews and approves each one of these parameters that gets added, and each one of them has a good reason for existing (even if we don't know what it is or believe its a good reason).
As a thought experiment I figured if I worked at Google how would I quantify the expense of a query parameter. Users don't really know or care what URLs look like anymore as long as the page is fast, so apart from measuring the gallons of tears generated on Hacker News, I guess resource usage would be the first logical thing to look at right?
Assuming every search is exactly like the one provided in the linked article, and using some public numbers from 2011 on searches/day, these are the top 5 parameters in terms of bandwidth used just transmitting the key and value to the server.
gs_l 42.3 Mbps
bav 11.7 Mbps
bvm 9.1 Mbps
fp 8.7 Mbps
sclient 6.1 Mbps
For just the top 5 thats almost 78 Mb of inbound data per second. Being sent over end users pipes (which are often limited by upload), hitting my transit and peering links, passing through my routers, hitting my front end load balancers, being turned into GoogleInternalProtocolX and fanned out to dozens of servers inside the datacenter over switches and internal routers, and being logged on durable storage for 18 months (assuming they dump this extra data when they strip personal information from the search record). Wow.
A general rule of thumb would be for every 20 bytes you add to URLs by way of keys or values, you've increased the overhead of almost every part of the Google infrastructure by 1 MB per second. (Note I did switch from bits to bytes in the final conversion, and this number is sourced from shaky data to start with)