Overriding contributed module functionality
A patch doesn't necessarily apply to a new version of a module: It is enough the patched function is moved to a different line, or the code for that function is changed, and the patch doesn't apply anymore. For the function to be moved to a different line, it is enough another function is re-written to take more lines (or less lines).

A better way to alter the behavior of a module is, for Drupal 7:


If the module uses code for a page callback that you want to change, change the page callback with hook_menu_alter().
If the module implements a theme function you want to alter, change the function associated with hook_theme_registry_alter(). In alternative, if it is sufficient to change the variables the theme function gets, then you can implement the preprocess function for that theme function (e.g. hook_preprocess_rdf_metadata() for theme_rdf_metadata(), and change the variables that theme function will get.
If the module executes an SQL query using db_select(), and assigns a tag to the query, change the executed query with hook_query_alter().
If the module implements a hook you don't want it is executed, you can implement hook_module_implements_alter() to avoid it is executed.
If the module implements an alter hook (e.g. hook_page_alter()), and you want to change what that hook altered, implement the same alter hook, being sure it is executed after the one implemented from that module.


In the case the function you want to alter is not a hook, then:


Check that function is using hooks implemented from other module. For example, node_save() invokes hook_node_presave(); if I would want to change the "changed" property of the node, I don't hack node_save(), but I rather implement hook_node_presave() to alter it.
Check that function is referenced/used from a hook; in that case, you can do something for that hook, as I previously described.


If anything I said until now doesn't apply, then it is better to create a custom module, and use the code of the other module to create it. I would also try asking a feature request for the existing module, hoping the feature is implemented.
Hacking a third-party module is never a good idea, especially because automatic updates of the module (via the Update Manager, or Drush) would not anymore possible for that module.