GUID stored in a varchar field I have inherited several databases that use GUIDs as PKs.  Instead of all the datatypes being uniqueidentifier most are varchar(50) and some varchar(100). Fields are true GUID some where created by 


  myID = 'xxx'+convert(varchar(40),newID())


In general its a bit of a mess

What are the performance implications for this design and is it worth re-working the tables to convert the datatypes.  Tables are generally around 1/2 M records with a couple table in the 2-4M record range.

The impetus of this question is that I am trying (unsuccessfully) to optimize an proc that joins 24 tables and views and the server is not handling it very well.

Thanks for any insight
In general, it is a bad idea to have long clustered index keys. For that it is not important if the key is made up of several short columns or few long columns. This makes the maintenance of every index as well as the read access of every index on that table a lot more expensive that it has to be. As the PK is by default enforced by a clustered index, you most likely have a very long clustered index key.

Also in general it is a good idea to have you clustered index key be monotonously increasing. As your column is valued based on NEWID it will distribute new rows all over the table causing fragmentation. The extra long key will make this even worse.

And finally, in general it is a good idea to not spend too much time tuning performance preemptively. If you do new development follow best practices (like the two recommendations above). With existing software, fix only the stuff that is causing a headache.

Now it looks like you have that headache already. Therefore I would start by migrating those primary keys to either identity columns (preferred) or to uniqueidentifier columns that default to newsequentialid().

But this is a difficult change to do if you can't take downtime. I that case I would start by adding new indexes to support you current strongest headache (read: stored procedure). Than work on cleaning up the mess afterwards.