Is adding indexes to a Drupal database safe?
Yes, it could result in problems.

If a module wants to do something with the column on which you have added an index, it will remove it's own indexes and then do whatever operation it intends to do.

What exactly will happen will depend on your database type and the actually executed operation. For example, a rename of the column will work fine with MySQL, but will fail on PostgreSQL. But if it tries to delete that column (maybe after migrating data to a different table/colun), it will fail.

The chances that this will happen are relatively low, at least for minor updates (does depend on the actual module however. I usually don't add any changes which could break something to minor releases), but it is possible.

My suggestion would be that you try to work together with the module maintainers. If the problematic query/ies are from the module itself, then the maintainers will probably happily add the indexes, if you provide a patch. Provide DESCRIBE output of the problematic query/ies before and after adding the index. Also provide a patch that updates the schema (include an update function to set it for existing installations).

Someone who is actively working on performance related things and does the above really well is catch, here is an example: http://drupal.org/node/983950