In the context of someone losing his wallet he says:
Il a dû tomber dans la rue.
Now what is the sense and form of tense being used?
I understand that devoir is conjugated as passé composé. (though dû could be used as adjective also). Given that the action is completed in the past, why is not the verb tomber conjugated (either in subjonctive since there is speculation, or past/passé composé since the action is complete?
It is conjugated. In the infinitive form. Okay, that was a bit tongue in the cheek, but it is true. Devoir takes (in this sense) an infinitive proposition, which is often just a verb in the infinitive
Je dois partir
Je dois manger
but can also be a complete propostion
Je dois partir en voiture manger à la Tour d'Argent avec Paul Erdős, qui vient juste de revenir à la vie.
with everything but the first two words being the argument of dois.
Now, if you want to know why it is an infinitive, you have trace back to Latin, which for seemingly arbitrary reasons made infinitive (of which they had three: past, present and future) mandatory for object propositions of a certain class of verbs.
It is now the only class of subordinate propositions that has no explicit subordinant (ie neither relative pronoun, nor conjunction…) and it only happens for a fixed set of verbs (see the corresponding Wikipedia article)
"Il a dû tomber" is a French way to say "He probably fell".
"Il a dû payer ses dettes" = He has had to pay his debts.
