Reclaiming space from a large partitioned database
I recently had a similar project where we implemented data compression on a partitioned table and reduced our space usage, resulting in the need to shrink down the files.  We did the following to manage this while keeping the database online:


Off hours DBCC SHRINKFILE executions.  We would start the shrink file off production hours and cancel it before the next day's worth of production started.  This would go on for several weeks, but progress on the shrink was not lost (as pages are getting moved towards the "front" of the file and aren't rolled back).  This did cause fragmentation, but the fragmentation was acceptable to our business in order to keep the database online during file cleanup.
Rebuilding individual partitions for the indexes.  If your table is partitioned, my view is that you should be doing this anyway because it minimizes the impact of the rebuild.  While we were doing file shrinks, we only did weekly index maintenance (we usually do daily)  in order to work with/around the DBCC SHRINKFILE.  Once we had reduced the filesize, we went back to daily index rebuilds.  In order to rebuild the individually fragmented partitions, we leveraged Ola Hallengren's scripts, but the essential command is ALTER INDEX foo ON bar REBUILD PARTITION=n.  You would run this command for each partition (n) that you wanted to rebuild.


This was a multi-week process for us, but we reduced a 1.5 TB file down to ~500 GB and did not interrupt the database service to do it.