Seems like recent FiveM updates brought new bugs.
Cars disappear when they get closer to a player from distance. If player gets closer to them, they also disappear. If you stand in one place for a long time, cars could start passing you by.
UPDATE: for the same reason (as I think) some car models does not load anymore (but were loading earlier). For ex., police, emperor, cheetah.
UPDATE 2: Recent update did indeed broke some things, but they are related to client addons being used.
Solved.