Sean,I've only been doing this for a year on my MT but I've noticed or read that parts like the EGR valve and the LAF sensor can contribute pretty significantly to poor mileage - and the life of both of these is limited. You could have a lot of other things going on. This can include vacuum leaks, grounding problems, bad sensors, deeper engine problems... that should be checked out and eliminated as causes - a real diagnosis. If you are paying a mechanic to sort them out, you should ask the forum to find one who is near you who knows Insights (@KLR3CYL on the west coast).
And you can do the valves in an hour, including learning how to do it. Adjusting the valves may make a BIG difference. This added 5 MPG and smoothed out the idle on mine. The cost is that of a feeler gauge and 10 mm wrenches. You may find they are way out of whack. I found that on both my CVT and MT.
I ended up replacing (fixing, actually) the EGR on mine, after building a tester to confirm it was bad. After testing a few other valves @jime and I concluded that these don't last very long. There are a lot of posts about EGR valves as a result, and a lot of cheap EGR valves sold on Ebay and Amazon. Some of these don't work. I know. I think @Natalya can point you in the right direction. It might not do anything, but at least it will eliminate a variable or a failure that will eventually happen.
I also replaced the LAF sensor with a Denso which is the OEM version for cars starting in late 2001. These you pretty much can't test (well, I just thought of a way, but it would take a LOT of work to build the tester) and if you have another problem, like a leaky head gasket or a ring problem, contamination may trash your new one. I spent a lot of time eliminating those as possible problems. I did eventually replace mine and the mileage increased quite a bit.
I got my CVT not long ago and I'm still learning to drive it. I can squeak out 60+ MPG if I baby the heck out of it but 43-49 MPG seems to be where it wants to live. I have not touched the EGR or LAF on these but I think the LAF sensor may be new. I need to run tests to see if my other sensors are performing correctly. I am also not running the super high mileage RE92s tires either.
Also, I'm still looking into this, but consider running 87 gas from a Top Tier station (google it) and maybe Techron (black bottle). If you are buying the cheapest gas you can find, well, it's a variable that you can control. My borescope and piston-top-cleaning experiments suggested that the best high-additive high-octane gas might not be the best for the car. But this is probably a minor factor at best.
I finally fixed the P0171 code (lean trim) and lack of IMA assist problem. Here are the things that did not fix the problem: 1. Cleaning EGR plate, 2. replacing the EGR, 3. replacing LFA and O2 Sensors, 4. testing for vacuum leaks, 5. Setting the valves. At almost 140k miles, all of the aforementioned items probably needed happen, so I do not feel bad about doing them. In the end, a new fuel pump assembly from Rock Auto fixed the problem. Thanks for your help, Mark