Because /usr/local/include is in the default include path, the include path and the library path are not consistent. The consequence is that (unless the user has modified the search paths with environment variables or switches) when some version of a library is installed in /usr (e.g., provided by the system) and another version of the library is installed in /usr/local (e.g., installed by the admin with configure, make, make install), the header file will be taken from /usr/local/include and the library will be taken from /usr/lib, but they do not correspond to the same version. For instance, this problem can be seen when GMP 4.1.4 is installed in /usr (as in Debian/stable) and the user installs GMP 4.2.1 (the latest version) in /usr/local (with configure, make, make install), as the gmp.h from GMP 4.2.1 is not compatible with the GMP library version 4.1.4. In short, gcc should make sure that include and library search paths are consistent *by default*. If the user wants a different search path, he can still modifie C_INCLUDE_PATH, LIBRARY_PATH and LD_LIBRARY_PATH (for instance) altogether.
Actually it is a bug that the library is not picking up and not a GCC bug. The library path is consistent with GCC's include path by default unless you messed up something. So this sounds like a bug in your installation.
(In reply to comment #1) > So this sounds like a bug in your installation. This cannot be with my installation in particular as the bug occurred on various Linux machines (only one is mine). However it could be due to bad defaults in Linux distributions. FYI, I've opened a bug here: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=395177 against libc6 (there could be a fix there), but perhaps ld should be fixed too, as the bug occurs whether -static is given or not.