A Vector igen, gyakorlatilag az összes metódusa synchronized kulcsszóval van ellátva. Az ArrayList-nek meg nem.
De nem a tartalomnak, hanem magára a Vector objektum monitorára lock-olnak ezek a metódusok (ajánlott irodalom: http://java.sun.com/docs/books/jls/second_edition/html/memory.doc.html)
Igen, ArrayList-nél előfordulhat, hogy az egyik szál add-ot hív, miközben egy másik szál éppen iterálgat végig a Vectoron... De ez akár egy 1 magos rendszerben is előfordulhat, ha éppen az iterátor szálat suspendeli a CPU ütemező, és a feléledő szálon pedig ráfut az add()-ra.
Ez egy nagyon jó könyv a témáról, ha érdekel: http://jcip.net/