I learnt when we use "provide" and "present" (not like "give", "offer", etc), we need to use "with".
"The hospital provided them with medicine."
Is "with" always necessary? If we removed "with", would the sentence sound unnatural?
The "with" is not necessary. I think its job is to help emphasize WHAT was provided (direct object of the verb) as opposed to WHO received it (indirect object of the verb). But that's usually clear from context, and the with is unnecessary.
The hospital provided them with medicine.
The hospital provided them medicine.
Both sentences are OK.
Note that sometime we use "provide" without any indirect object, and then you definitely don't use the "with."
Many different agencies provided support. The hospital provided medicine.
So: All three of these forms are fine, and the first two are equivalent to each other:
provide (somebody) with (something)
provide (somebody) (something)
You can also have: "The hospital provided medicine to them."
What about "The hospital provided medicine FOR them."?