When does an under the sink P-Trap assembly need venting?
All traps need venting in all cases. Without a vent, the water seal in the trap gets sucked out and sewer gases can enter the room. There's also all sorts of examples where someone thought they were providing venting, but done in such a way that clearing the water seal was still a possibility. Some of these methods even used to be accepted practice, such as S traps. There's still several appropriate ways to achieve proper venting. For example, in island sink situations, a loop or foot vent is acceptable.

It's hard to say why the previous installation worked without venting. For sure, one way or another, the siphon action was disturbed by the entrance of air somehow, either from oversized pipe or leaking fittings. Regardless, where do you go from here? The downward facing ell in wall needs to be replaced with a sanitary tee for starters. The top of the new tee needs to tie into a vent somewhere, without travelling downwards. Is there a vent pipe nearby, such as from a toilet or shower? Or a pipe could perhaps be extended up into the attic, where it should be much easier to make a run to a vent pipe?

If all that sounds like too much, get a mechanical vent such as jberger suggested. They are not accepted by many codes, but they do work. Just be sure it's attached to a long enough pipe so that the valve is above the flood level of the sink. No doubt this all sounds like a real PITA right now. Once it's all done, you can take pride and sleep well knowing you have a properly functioning and completely sanitary sink drainage.