Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?
I think this is really a question about the API features. Access to an older version, in Driscoll et al.'s sense, requires a pointer to that version, not just a predicate used to traverse a version tree to locate the version.

For a similar API/modelling question, you can look at the question of how long delete takes in a priority queue. Plenty of papers advertise that they offer $O(1)$ delete, but this assumes one already has a pointer to the item to be deleted.