Thanks for the responses!
Each client needs to have many media placements associated with them, and they need to be easily updated. Also, both clients and media placements need full "Post" capability. Meaning editable with TinyMCE, Queryable, etc.
Bheadrick, originally I had solved the issue by doing exactly what you suggested. Clients and Media Placements were both part of the same custom post type, "Clients & Placements", and I would associate Media Placements with a Client by making them a child of that Client.
The problem with this setup is that administrating the system becomes extremely unfriendly, since the large number of placements makes the interface for picking a parent post (the "Parent" drop down in the "Attributes" box) extremely unwieldy. The client was not happy with it.