This is actually a question that came up way back when Mines of Moria came out -- people wondered what would happen if you tried to use
the Bridge of Khazad-dum to play the Balrog from your deck, but couldn't find the Balrog in there.
As a result, there's actually a section in the comprehensive rules document (page 11) that says, "There is no penalty if you don't find (or choose not to play) a card you are looking for in your draw deck."
So, yeah. You can use Sam as much as you'd like. =P
UPDATE: I was just about to hit the Post button, but I decided to read up on the section on Loops in the comprehensive rulebook first. Strangely enough, Sam is actually the example they use in this section:
"If a loop contains one or more optional actions and one player controls them all, that player chooses a number. The loop is treated as repeating that number of times, or until another player intervenes with his own action, whichever comes first.
A player wishes to repeatedly use the ability of
Sam, Faithful Companion ("Fellowship: Play
Bill the Pony from your draw deck."). He chooses a number of times this action will take place. The action is treated as repeating that number of times unless another player intervenes with a different action."