List.Contains() is very slow?

If you are just checking for existence, HashSet<T> in .NET 3.5 is your best option – dictionary-like performance, but no key/value pair – just the values:

    HashSet<int> data = new HashSet<int>();
    for (int i = 0; i < 1000000; i++)
    {
        data.Add(rand.Next(50000000));
    }
    bool contains = data.Contains(1234567); // etc