I know some stores tend to stock it, some don't.
One year before Pesach I tried contacting a produce wholesaler (we were having lots of company) regarding buying a case of it -- they said they contacted Dole and Dole said they would send a case WITH the Star-K kosher stamp. Well then the lettuce arrived and it didn't have the Star-K on it.
VEG./SALADS, FRESH PKGD. All fresh packaged salads bearing the Star-K symbol are Kosher for Passover without any additional Passover symbol. Please note exception: Dole Very Veggie Salad Blend contains peas which are Kitniyos and may not be used on Passover.
Updated in 2011: Fresh Express salads require Star-K-P for Passover.
So this would be ideal for easy marror for large crowds (if I could order a case of the giant bags of romaine).
Pesach or otherwise, any ideas? Somehow some stores are able to get it ...