It looks like some type of Osmanthus to me. There are quite a few different species: O. heterophyllus, O. yunnanensis, O. fragrans (sweet olive), and many, many more! I think Home Depot's picture of their plant has the most resemblance to your photos:
Osmanthus can be gigantic trees or small shrubs, or can be trimmed to become hedges. Some bloom in the fall, and some in spring.
The reason I think of Osmanthus and not Pittosporum is the way the little flowers look, hiding amongst the leaves, and also the way you describe the fragrance, "... immaculate, so strong, smelt from far away, yet soft and perfume like at the same time."
The fact that you use the word "immaculate" sounds more like O. than Pittosporum which is so overpoweringly fragrant it can be cloying and unpleasant at close range. (my opinion, sorry)
Osmanthus does have a heavenly fragrance that for some reason can be very hard to pinpoint where it's coming from. Maybe because the flowers are so nondescript and "shy", you don't suspect (or even notice) them right away.