But then there is always this feeling that these joins are going to make things complicated, verbose, and inefficient, when a simple enum or an array column would be simpler.
My main gripe is that I hate having to impose constraints on my data model early on when I have no idea about how it will evolve over time.
How do others deal with these decisions?
Also, is there any product that would allow me to model the domain exactly as it is (i.e. like a semantic graph), and then have efficient and simple querying?
For example if you have an invoice line, it belongs to an invoice. The DB will ensure that for you with a foreign key. If you stick a join table in the middle to make it many to many, you can now have a invoice line that belongs to many invoices.
That is probably not what you want, and if it isn't the DB is asking your application enforce the constraint that it could have easily enforced itself.
And that means you are not getting the advantages of an enforced schema!
To answer your actual questions, I'd go for the most constraining option first (which is usually the easiest to implement) and then open it up to many to many later if required. That might need an 'upgrade' script, but that is par for the course in DB design.
It sounds like you are most comfortable with the many-to-many approach, so I recommend using that option. Don't worry about hypothetical future problems that this approach may or may not bring. You can always change it later if it becomes a problem.
YAGNI: https://en.wikipedia.org/wiki/You_aren%27t_gonna_need_it