This works fine without -fuse-linker-plugin (with all object files extracted from archive). This reduced testcase has some undefined references of its own but still exposes the bug as shown below. Whole output of linking a complete program is attached because of its 30 kB size. Also a preprocessed source file is attached.

gcc -std=gnu99 -fvisibility=hidden -O3 -fomit-frame-pointer -march=pentium4 -flto -fuse-linker-plugin -o xz main.i

--SNAP--
/home/misty/gcc/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../i686-pc-linux-gnu/bin/ld: error: hidden symbol 'fgetc' is not defined locally
/home/misty/gcc/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../i686-pc-linux-gnu/bin/ld: error: hidden symbol 'ferror' is not defined locally
--SNAP--

main.i was produced with:

gcc -std=gnu99 -DHAVE_CONFIG_H -I. -I../..  -DLOCALEDIR=\"/home/misty/gcc/share/locale\" -I../../src/common -I../../src/liblzma/api -I../../lib -DLZMA_API_STATIC  -pthread -fvisibility=hidden -Wall -Wextra -Wformat=2 -Winit-self -Wmissing-include-dirs -Wstrict-aliasing -Wfloat-equal -Wundef -Wshadow -Wpointer-arith -Wbad-function-cast -Wwrite-strings -Wlogical-op -Waggregate-return -Wstrict-prototypes -Wold-style-definition -Wmissing-prototypes -Wmissing-declarations -Wmissing-noreturn -Wredundant-decls -O3 -fomit-frame-pointer -march=pentium4 -flto -fuse-linker-plugin -MT xz-main.o -MD -MP -MF .deps/xz-main.Tpo -E main.c >main.i