Adds itest for search.

Fixes storing stuff we shouldn't in StoreOperation, including
isDeleted which apparently WILL SILENTLY BREAK SEARCH.

Closes #299