are there any scenarios where using starting_key might lead to unexpected performance/behaviour? (while still being a better option than iterating through the whole set)

The cursor is always something that the server first sends to the client, and the client then uses for a subsequent request. It's not a client-controlled field (or if a client does modify it, we don't care about supporting the changes they make).