list manipulation - Delete with multiple indices is extremely slow--workaround?

Delete is unbelievably slow when deleting multiple elements from a non-packed array.

Is there a robust workaround that will work on any non-packed array?

inds = List /@ RandomSample[Range[100000], 50000];
Delete[Developer`FromPackedArray@Range[100000], inds]; // AbsoluteTiming
(* {17.8957, Null} *)

On packed arrays it performs as expected, but my array cannot be packed. It does not necessarily contain numbers.

inds = List /@ RandomSample[Range[100000], 50000];
Delete[Range[100000], inds]; // AbsoluteTiming
(* {0.005767, Null} *)

---

I did not try to test for this, but one possible explanation is that even when given multiple indices, Delete will delete elements one-by-one, re-allocating the array after each step. If someone feels like testing it, you can try to see if the timing is quadratic in the number of elements deleted.