All of that solved by the unrolled-list mockup. It works, and works with scdr, no matter how many pointers point in the middle of otherwise-proper lists, and even works with lists split by scdr, handling both the parts before and after the scdr-split seamlessly. Costs are also not very large - mostly the added cost is in the search through cdr-table for the next highest key. That said the added cost is O(n) where n is the number of individual cons cells scdr has been used on.
So yes, the above code you show will add cost. But how often is it used in actual coding anyway? The most common use of cons cells is straight sequences, and quite a bit of arcn can't handle improper lists (quasiquote comes to mind) - yet arc is useful enough to write news.yc.
Edit: Come to think of it, for the common case where scdr completely trashes the old cdr of a cons cell (i.e. no references to it are kept), the linear lookup through cdr-table will still end up being O(1), since keys are sorted, and the earlier cdr-table entry gets found first.
