I understand that in order to say that something (or someone) is absent or does not exist, we use the genitive case and не было, such as:
Его здесь нет.
Его там не было.

But I have seen some...