The "no version information available" means that the library version number is lower on the shared object. For example, if your major.minor.patch number is 7.15.5 on the machine where you build the binary, and the major.minor.patch number is 7.12.1 on the installation machine, ld will print the warning.
You can fix this by compiling with a library (headers and shared objects) that matches the shared object version shipped with your target OS. E.g., if you are going to install to RedHat 3.4.6-9 you don't want to compile on Debian 4.1.1-21. This is one of the reasons that most distributions ship for specific linux distro numbers.
Otherwise, you can statically link. However, you don't want to do this with something like PAM, so you want to actually install a development environment that matches your client's production environment (or at least install and link against the correct library versions.)
Advice you get to rename the .so files (padding them with version numbers,) stems from a time when shared object libraries did not use versioned symbols. So don't expect that playing with the .so.n.n.n naming scheme is going to help (much - it might help if you system has been trashed.)
You last option will be compiling with a library with a different minor version number, using a custom linking script:
http://www.redhat.com/docs/manuals/enterprise/RHEL-4-Manual/gnu-linker/scripts.html
To do this, you'll need to write a custom script, and you'll need a custom installer that runs ld against your client's shared objects, using the custom script. This requires that your client have gcc or ld on their production system.