I've also tried using different 7805s (I have about 20, though they're all from STMicroelectronics) and various capacitor configurations).
Have you considered using the capacitor configuration recommended by the manufacturer here: http://www.st.com/stonline/stappl/st/analog/product/63279.jsp ?
Don