How to completely uninstall a package (including all extra files that came with it) using yum (or rpm)?

Check the Deleting packages with yum section in the HOW TO

There says:

In any event, the command syntax for package removal is:

   # yum remove package1 [package2 package3...]

As noted above, it removes package1 and all packages in the dependency tree that depend on package1, possibly irreversibly as far as configuration data is concerned.

As a quick way you can try:

yum remove package
yum install package

Also here is an interesting for. And the question can help you.

The one that keeps configs in a backup is rpm -e

What you can do is find out what is in a rpm using:

 rpm -ql packagename

or

rpm -qlp packagename if the package is not yet installed.

then, you can manually make the modifications you want.

Hope this helps!