How do shrink *right* when required?
The recommendation from your Providers DBA is sufficient for your needs.  I would add the additional step of checking to make sure you don't have any heaps, however.  When you delete records from Heaps the space is not always made available and you won't have a good way of reorganizing it.  If you can, add a clustered index to the heap before deleting (or after, dealers choice).  If you cannot, I would delete, add a clustered index and then remove it.  

SELECT T.name AS TableName
    , I.* FROM sys.indexes AS I
    INNER JOIN sys.tables AS T ON T.object_id = I.object_id
WHERE I.type_desc = 'HEAP'


So, my steps would be:


Check for Heaps and decide on course of action. 
purge data (preferably in chunks), check-pointing or backing up the log as
applicable. 
defragment indexes (Ola Hallengren's scripts will help
here if you don't have your own).  Do this first so that pages can be readjusted to the correct fill factor.  Otherwise, space used estimate will be off since a partially used page is counted as a full page and you will probably have lots of partially full pages that can be consolidated without impact.
Look at current database file size
used.  Shrink to appropriate size (I like to leave at least 20% empty
space in the file.   
Defragment your indexes again since the shrink moved everything around.
Take the time to evaluate file growth settings
to make sure they make sense for your environment.  Usually growing
in fixed size rather than as a percentage and make sure you have
instant file initialization turned on.


This will tell you how much space is actually being used in the file.

SELECT DB_NAME() AS DatabaseName
, F.name
, F.type_desc 
, F.state_desc 
, F.file_id 
, F.growth 
, F.max_size
, F.is_percent_growth
, F.physical_name
, F.size/128.0 AS CurrentSize_MB
, FILEPROPERTY(F.name, 'SpaceUsed')/128.0 AS SpaceUsed_MB
 FROM sys.database_files F