Update for whoever finds this topic and has the same problem:
I've contacted MS Support and after further testing, long story short, the issue has been escalated to the product team. I'll post another update asap.
Just to clarify the problem we found during testing: we create an "When an item is created (V2)" trigger which will only trigger once. It won't trigger again later. In my case the trigger checks for new data every minute and it never finds new data in the database even if new rows were inserted in said database.
Final update:
The product team informed me the following:
"The way trigger works is we keep polling sql with the largest value in the ID column we have seen. Whenever sql gives us a bigger number the trigger fires and we store the new number."
Indeed, I was using a table to test the flow so I kept truncating the table before a new run.
So, the trigger kept the last ID there was in the table (lets say, 6) and I truncate the table. Next time I ran the test flow a new row was created with ID 1, so the trigger wouldn't fire. I never ran the test flow enough times to have an ID bigger than 6 so the trigger never fired again. After that reply from the Product Team, I ran the flow enough times to increase the ID after 6 and the trigger worked after that.