Ensure `Store.Exists()` looks up the correct device ID

Extracted from #102.

@bbangert r?