Miért éri meg egy cégnek hónapokig keresni egy kollégát?

Nem feltétlen. Nyilván, ha még midig keresik akkor az előző kolléga még nem hagyta el a céget, hiszen valaki elvégzi a munkát.

Ha párhuzamosan felvennének egy betanításra szorulót akkor 2 bért kéne fizetni - ez egyrészt nem mindenhol lehetséges, ahol FTE-kre épül a bérköltség, másrészt pedig akkor a betanuló nem végezne a cég számára hasznos munkát.

Azt meg ha jól értem egy szóval sem mondták, hogy azonnali kezdést várnak el. Csak azt, hogy a kijelölt időponttól (mondjuk mikor szülni megy az előd vagy mikor lejár a szerződése/felmondása) rögtön 100%-osan át kell tudni venni a helyét.

Logikus, amit az előző válaszoló ír. Ettől függetlenül, az is lehetséges (nem ismerem a céget), hogy nem voltál nekik szimpatikus valamiért, és nem a valódi okot mondták meg.

Persze az igazi okot csak ők tudják.

Ne foglalkozz vele, találsz jobbat. :)