The fact that the table was made from untreated, big box store 2X stock pretty much answers your question. That wood is almost certainly what is known in the trade as SPF (meaning, spruce, pine or fir, but probably not fir), and untreated, it has very little rot resistance. Left outside, water got under the planking, kept the structural 2X underneath continuously damp, and voila, it was too unsound in a few years to hold the screws.
So, what could you have done to prevent this: First, use treated lumber, or, if you want to spend the money, a rot resistant species like cypress, white oak or redwood. Second, construct and position the table so that water is unlikely to be able settle between boards, and will run off all horizontal surfaces. Treated lumber will generally not tolerate continuous moisture exposure, unless it is rated for ground contact. Even then, it'll last better if it doesn't stay wet.
Deck screws (assuming they were long enough) are ok for this application if the table is going to stay put. Personally, though, when I've built outdoor tables, I've used galvanized 5/16" carriage bolts, bolted through the structural members. People like to pick picnic tables up by the table planks and otherwise put loads on the fastenings that deck screws aren't designed to handle. Through bolts with larger heads take the abuse better.
One possible approach to consider is to get a steel kit for the support structure of the table, and use wood for the seats and table top only. Typically these are made of tube steel, and require using through bolts. Solves the moisture entrapment problem. They are also lighter than wooden support frames. I just replaced the seat and table boards on a table I built with tubular steel supports 41 years ago. The boards were Douglass Fir, so fairly rot resistant, and we kept them sealed for the most part, but they were outside continuously for those 4 decades, and most of the wood was still usably sound, although definitely close to end of usable life.