"Could not find type for id" error when traversing graph / Corrupted label in a vertex

The schema is pretty simple (few labels, properties, constraints and indexes).
- JanusGraph 0.4.1
- Storage Backend: Scylla 3.2.0
- 40k vertices

For me it looks like one day in the database appears a broken vertex which makes impossible to run any queries that iterate all vertices and contains "hasLabel()" method.
We are still investigating this issue, but it does not seem like any schema changes were made right before we noticed it last time.
This is how it looks:

```
gremlin> g.V().hasLabel('userProduct')
12:05:44 WARN org.janusgraph.graphdb.transaction.StandardJanusGraphTx - Query requires iterating over all vertices [(~label = userProduct)]. For better performance, use indexes
Could not find type for id: 155149
Type ':help' or ':h' for help.

gremlin> g.V().hasLabel('nnname')
12:49:34 WARN org.janusgraph.graphdb.transaction.StandardJanusGraphTx - Query requires iterating over all vertices [(~label = nnname)]. For better performance, use indexes
Could not find type for id: 155149
Type ':help' or ':h' for help.
Display stack trace? [yN]
```

Meanwhile method "has()" works fine:
```
gremlin>
gremlin> g.V().has('name', 'ddd')
12:24:37 WARN org.janusgraph.graphdb.transaction.StandardJanusGraphTx - Query requires iterating over all vertices [(name = ddd)]. For better performance, use indexes
==>v[368767136]
==>v[123867144]
gremlin>
```

When trying to get that vertex properties we get only (`[id:155149,label:vertex]`):
```
gremlin> g.V(155149)
Could not find type for id: 155149
Type ':help' or ':h' for help.
Display stack trace? [yN]

gremlin>
gremlin> g.V(155149).count()
==>1

gremlin> g.V(155149).elementMap()
==>[id:155149,label:vertex]
gremlin>
```

P.S.
The problem is critical and already reached our production database...:((

Start by reproducing the reported g.V().hasLabel(), g.V(155149), and elementMap() behavior on JanusGraph 0.4.1 with the described Scylla 3.2.0 setup. Capture the stack trace when "Could not find type for id" occurs and compare the affected vertex with the working has() query; the issue is complete only when the corruption cause and a verified remedy are identified.

Written by the indexing model from the issue text.