Thank you very much for the detailed replies. Part of the problem is that this garden is located miles away from where we normally live (8 hour drive by car). So I can't always be on top of the weeding chores. Also the garden was rototilled several times by a nearby farmer, and later on by myself. This definitely made the problem worse. The soil is quite sandy, which easily compacts and gets very hard in the dry season. The region has Mediterranean climate, which means no rain roughly between May through October. So the garden is irrigated with drip irrigation.
I really think that deep garden beds is going to be the answer. I am thinking of stacking three 2x4's along the length of the beds as border (about 25 meters = 75 feet). This is not going to be cheap for sure, but maybe I can think of a cheaper border alternative. Please let me know if you have better ideas to make the borders for the deep bed. Could borderless be an option? Then of course I need to add good quality soil and mulch. I also thought that if I had softer soil pulling this weed could be much easier.