With the bisection method and a relative stable validator set you can expect to see large porosity in the trusted store. Many headers are missed and therefore not validated. At the moment VerifyHeader() runs the single check of making sure that the height of the untrustedHeader is greater than the trustedHeader stored in the client. This means that untrustedHeaders that are not greater in height to the one stored in the lite client (usually the latest) must be verified via fetchMissingTrustedHeader() which then runs the backwards verification. I would propose therefore that we use a single method that returns a trusted Header by checking if it is in the store and then if not, using a single verifyHeader function to verify the untrusted Header from the nearest trusted one (either sequence, bisection or backwards). To do so, I would replace these functions of the store interface:

// LastSignedHeaderHeight returns the last (newest) SignedHeader height.
//
// If the store is empty, -1 and nil error are returned.
LastSignedHeaderHeight() (int64, error

// FirstSignedHeaderHeight returns the first (oldest) SignedHeader height.
//
// If the store is empty, -1 and nil error are returned.
FirstSignedHeaderHeight() (int64, error)

// SignedHeaderAfter returns the SignedHeader after the certain height.
//
// height must be > 0 && <= LastSignedHeaderHeight.
SignedHeaderAfter(height int64) (*types.SignedHeader, error)

with

// Heights returns all the heights of the headers that the store has. 
Heights() ([]int64, error)

which in a key-value database should just be all the keys

That way we simplify the interface and we can very quickly check if a header is in the store and if not, which is the closest header we can use to verify the untrusted header from.