It is generally a good idea to build a cross-toolchain that uses the same version of libc (and other libraries) found on the target system. This is especially important in the case of libraries that use versioned symbols or you could wind up with errors like "/usr/lib/libstdc++.so.6: version 'GLIBCXX_3.4.11' not found".
Same Architecture
For generating executables for standard Ubuntu 8.04 and CentOS 5.3 systems, you could install the distributions in virtual machines and do the necessary compilation from within the virtual machine to guarantee the resulting binaries are compatible with the library versions from each distribution.
Another option would be to setup chroot build environments instead of virtual machines for the target distributions.
You could also build toolchains targeted at different environments (different library versions) and build under your Ubuntu 9.10 environment without using virtual machines or chroot environments. I have used Dan Kegel's crosstool for creating such cross-toolchains.
Different Architecture
As I noted in my answer to a another cross-compiler question, I used Dan Kegel's crosstool for creating my arm cross-toolchain.
It appears it may be slightly out of date, but there is a matrix of build results for various architectures to help determine a suitable combination of gcc, glibc, binutils, and linux kernel headers.
Required Package Versions
In my experience, there really isn't a rule of thumb. Not all combinations of gcc, binutils, glibc, and linux headers will build successfully. Even if the build completes, some level of testing is necessary to validate the build's success. This is sometimes done by compiling the Linux kernel with your new cross-toolchain. Depending on the target system and architecture, some patching of the source may be necessary to produce a successful build.
Since you are setting up this cross-compilation environment on Ubuntu 9.10, you might want to look into the dpkg-cross package.