Thanks, perhaps a bit more background is in order.
I'd like an idea for what kind of impact having no primary, clustered keys at all would have on your typical transactional database...
A lot. The heap would be a big slow-down.
Is there an identity-type column (int or bigint) on any table?
You can likely change the underlying indexing to clustered and rebuild all indexes, and gain performance, without impacting the app. Can you set up a test environment to verify this and to regression test before running such a script on production? You may not be able to specify PK in the DDL, since that brings restrictions along with it. But you can still create an unique clustered index on the natural primary key and achieve the identical effect.
Obviously, with no defined PK, features like replication are not going to be a future option. If there is an unique identity key (a sequential integer field), you can cluster that column and reap maximum indexing benefits, especially since inserts will always go to the end of the cluster.
Then once you get indexes clustered on all tables, go find Michelle Ufford's dba_indexdefrag freeware and schedule yourself a weekly index rebuild job that runs on a weekend schedule. If you wish, another step to the same job could update statistics, and you would reap best speed and keep your DB nice and clean.