Use of have as auxiliary emphasizes that an action is completed. Though both forms are going to be properly understood in context, you would generally use the have version when dealing with an action that started and finished at an identifiable point in the past.
As I see it, the following are to be preferred w/o have, since they refer to activities which are either ongoing or intermittent:
Thomas denied taking the metro to work on Wednesdays.
being a stamp collector.
On the other hand (as most typically occurs with allegations of criminal acts), if the event has a definite starting and end point, then the have version is preferred:
Thomas denied having taken the metro on Wednesday January 8th
Thomas denied having purchased the Three Dragons stamp.