In Postgres9.1 a new feature was implemented [1] for adding PK and UNIQUE constraints using indexes created concurrently, but constraints NOT NULL and CHECK still require full seqscan of a table. New CHECK constraint allows "NOT VALID" option but VALIDATE CONSTRAINT still does seqscan (with RowExclusiveLock, but for big and constantly updatable table it is still awful).
It is possible to find wrong rows in a table without seqscan if there is an index with a predicate allows to find such rows. There is no sense what columns it has since it is enough to check whether index_getnext for it returns NULL (table is OK) or any tuple (table has wrong rows).
You avoid a full seqscan by creating an index which also does a full seq scan.
How does this help? The lock and scan times are the same.
--
Simon Riggs http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services