Quite the opposite. Insertion time will be increased (by a
small constant factor) over randomly ordered input. The
result will be well balanced though.

Red-black trees *avoid* the problem that unbalanced trees have with
presorted data. If the data is inserted in key sequence an unbalanced
tree algorithm will insert each new node as the right brother of the
rightmost node, so you end up with a tree that has degenerated into a
list and, as you'd expect, search performance is horrid. Reverse sorted
data is just as bad: you still end up with a fully degenerate tree but
this time it grows on the left.

The red-black tree avoids this problem because it re-balances as needed
after each insert: this adds a small overhead but all branches are the
same length within +/- one node. The overhead is small because
rebalancing just involves swapping pointers, not moving or reallocating
nodes.

The bottom line is that unbalanced trees should be fed unsorted data and
will still have unequal branch lengths, but red-black trees are
unaffected by data ordering.

If you want all the gory details for different types of tree, find a
copy of "Algorithms" by Robert Sedgewick (pub. Addison-Wesley).

====
One caveat: the performance of red-black binary trees is critically
dependent on the data structures used to build the tree and on the
performance of the memory allocator. Here's an illustration:

The standard C implementation uses a hidden structure made of small
nodes. Each holds three pointers (left & right brothers plus one to the
user-defined structure holding the key and data). Hence, adding a node
requires two separate memory allocations for small bits of memory. This
can be brain-hurtingly slow compared with an algorithm that's optimized
to use one structure for key, data and pointers and that grabs large
chunks of memory so it can store lots of nodes in each chunk.

I did such an optimization on a 150 MHz Alphaserver running Digital Unix
(yeah, that long ago: 1997). I had enough test data to build a tree with
200,000 nodes (6.5 MB for the tree) so the measurement statistics were
pretty good. My initial implementation using the standard C library
loaded the tree at 700 inserts/sec. Each insert involved a tree search
to find the insertion point, two memory allocations and a pointer
adjustment to rebalance the tree. My first rewrite used  optimized code
swiped from Sedgewick and combined the pointers and data into a single
structure. This got me up to 1500 inserts/sec during loading, but I
needed better than 3000 inserts/sec to hit the system performance
target. My final rewrite introduced a custom memory allocator that was
optimized by making a few requests on the OS for large chunks of memory
and fit lots of nodes into each chunk. The first chunk requested was 1MB
and this doubled for each successive request. The tree loading speed
went up to 17,000 inserts/sec. Obviously the Digital Unix memory
allocator was rather inefficient!

The TreeMap class may well have the same performance problem because it
too uses a hidden structure to define the tree but adds TWO memory
allocations because the key and data are two separate object instances.
This has to give a performance hit but the size of the hit depends
entirely on the efficiency of the JVM memory allocator.

HTH

You say that the list will be scanned and weeded once a second. The
optimum storage structure depends on the proportion if scans, searches
and alterations per second, i.e., if several hundred items are retrieved
 per second, then the efficiency of scanning the complete set of items
is relatively unimportant unless it interferes with item retrieval.

Do you have any statistics or estimates on the number of:
- items read per second
- items added per second
- items removed per second

If you don't ever need the items in a sorted order (an order
other than insertion order) then a TreeMap will be of no
benefit over a hashed data structure. If you never need to
look up items by some key, which is starting to sound like
the case, then a hashed data structure will be of no benefit.
In other words, if you're just adding new items to the end
of the list, scanning through the list to remove items, and
using the items in some way as an unordered set, then use
a LinkedList or an array or ArrayList (with the efficient
scan/remove procedure I posted earlier). Using a fixed-
size array that is big enough or doing your own array
growing/shrinking if necessary will be the fastest. Using
a LinkedList will result in the simplest code.