In a match against someone (a professional), I was faced with a Tyrant's Machine. He tapped my best creature and he said that my permanent never untapped, not even during my untap step. Needless to say, I lost. Was he correct?
This would actually depend on which phase he tapped your creature in. The phases of a turn go in this order:
Untap > Upkeep > Draw > Main > Combat > Main > End
So there is a point, between your untap and draw step, in which he could tap your creature until your next turn. This explanation does not account for him saying that the creature didn't untap during your untap step. There could also have been some other effect on the board that would stop your creature from untapping during your untap step (aka hard tapped). However, without knowing the rest of the board state, that is impossible to tell.