Arraylist.Contains ... "Index was outside the bounds of the array"

Every once in a while we get an "Index was outside the bounds of the array" error on a Arraylist.Contains call. 
The Arraylist instance itself exists, but trying to find out if it contains a specific value/element throws this error. I would expect a true/false answer from the Arraylist, not an error.
What might cause this issue?
...