I've read something to the effect that the HMAC construct is able to lessen the problem of collisions in the underlying hash.
Does that mean that something like HMAC-MD5 still might be considered safe for authenticating encrypted data?
Yes, there are currently no known attacks on HMAC-MD5.
In particular, after the first collision attacks on MD5, Mihir Bellare (one of the inventors of HMAC) came up with a new security proof for HMAC that doesn't require collision resistance:
However, this does not mean you should use HMAC-MD5 in new cryptosystem designs. To paraphrase Bruce Schneier, "attacks only get better, never worse." We already have practical collision attacks for MD5, showing that it does not meet its original security goals; it's possible that, any day now, someone might figure out a way to turn those into a preimage attack, which would compromise the security of HMAC-MD5. A much better choice would be to use HMAC with a hash function having no known attacks, such as SHA-2 or SHA-3.