There have existed for a long time a paradigm that TiO phases at ambient conditions are stable only if structural vacancies are available. Using an evolutionary algorithm, we perform an ab initio search of possible zero-temperature polymorphs of TiO in wide pressure interval. We obtain the Gibbs energy of the competing phases taking into account entropy via quasiharmonic approximation and build the pressure-temperature diagram of the system. We reveal that two vacancy-free hexagonal phases are the most stable at relatively low temperatures in a wide range of pressures. The transition between these phases takes place at 28 GPa. Only above 1290 K at ambient pressure the phases with vacancies (B1-derived) become stable. In particular, the high-pressure hexagonal phase is shown to have unusual electronic properties, with a pronounced pseudo-gap in the electronic spectrum. The comparison of DFT-GGA and GW calculations demonstrates that the account for many-body corrections significantly changes the electronic spectrum near the Fermi energy.