>> I've been working a little bit with a few tables here, they've got "CreatedDate" as clustered Index and and Id (UniqueIdentifier) as Primary Key. The Id's are generated from code and are non-sequential.<<
Why do you think that your unique identifier can ever be a key of any kind? By definition, a key is a subset of columns (attributes) in a table, which is always unique. Ever read anything about RDBMS by Dr. Codd or anyone else? GUIDs are global, like the letter "G" says, and not part of the logical data model in the table.
Serious RDBMS people refer to programmers like you as "ID-iots" because they try to use a non-attribute as a key in a table. This derogatory term also applies to people who use IDENTITY or AUTOINCREMENT vendor extensions for keys. Your logical fallacy is that while a key is unique, being unique does not make something it a key.
>>Should we consider some kind of redesign of the table? <<
Since this thing does not have a proper key, is not yet a table by definition, please consider starting over on the whole schema.
Please post DDL and follow ANSI/ISO standards when asking for help.