It sounds like you need both clients and projects to have “post-like” capabilities, meaning that using a taxonomy for clients wouldn’t make much sense. In this case, I would highly recommend the amazing “Posts 2 Posts” plugin by Scribu, found here: http://wordpress.org/extend/plugins/posts-to-posts/
The plugin allows you to create connections between posts, and makes it trivial to query posts based on these connections.