Is yours the late 2004 model? I had the exact problem! I got 4GB from OWC, and one stick just wouldn't be noticed by system profiler. I had to exchange the weird stick with OWC, and the new one works.
I did notice on the one that would never work as part of a pair(I tried all combinations and it was one), the only physical anomaly was a different number on the black chips on the front side. Neither me or OWC knew how that could link to the issue, or why it was different, but you might wanna check your sticks. Is it more than one?