I have some state ids which do not exist in sde.versions table. They are found in sde.states and sde.state_lineages.
Is this a normal thing or does it mean there is a problem in our database?
That is normal.
The Versions table shows the current state that the Versions are pointing to.
This link should give you more details about the System Tables: System tables of a geodatabase stored in Oracle—Help | ArcGIS for Desktop