When all you indexes have included all the other columns, do you still have the penalty for a wide clustered index?
If you have in every index all columns and you have a PK , and another 2 indexes , one on Value and one on LastChanged , you really multiplied the table by 4. This will make the table really slow for all operations. 

Add an ID column , make it PK  and build indexes as you need based on the statements that run on the table. 

Don't create an index on Invalid, it's a bit column , it's usually not useful . 

Try to keep a rule that all indexes should be smaller in size than the table.