We have Calphalon non-stick cookware and it seems, after 5 years, not to want to get clean. Even the best scrubbing leaves kind of a hazy look on them. Additionally, the exterior of our most used pan is darkly stained, kind of like a well-seasoned cast iron pan. Is that okay, or do I need to clean it better too?
I'm gonna assume you're talking about pans with a hard anodized exterior and non-stick interior...
The anodized exterior will pick up stains over time, and you probably shouldn't worry too much about trying to get them back to factory condition. That said, you can find some tips on How should I clean anodised cookware? - I use baking soda and elbow grease for routine jobs, and occasionally resort to Ajax (scouring powder) for touch-up around the handle.
The non-stick interior is probably just wearing out. AFAIK, some Calphalon non-stick pans have a texture to them that is supposed to improve browning, but over time even smooth non-stick surfaces develop pits and scratches that create opportunity for residue to hold on to. I use a bit of baking soda and a bit of salt to scrub these clean, but once something gets stuck on to the point where serious scouring is necessary to remove it you'll just have to give up (since that would take the non-stick coating with it). Non-stick pans - even well-made ones - do tend wear out faster than ordinary pans, and there's no getting around that.