Hi there, hope i can help you on this one. It looked like a problem I am familiar with, and I looked it up and found that there is a technical service bulletin from mitsubishi, TSB-04-13-007 which covers both the 2003 and 2004 Lancer EVO's for a random misfire code. Unfortunately, you will have to take it to the dealer for this concern because it needs to have the ecu updated/reprogrammed. I don't know what your in service date is, but that is covered under warranty for 8 years or 80,000 miles, whichever occurs first. Let me know if you need any further help with this.
It is possible that something in the drive train/clutch could cause a problem like this, especially since you never had the check engine light come on before the clutch was replaced. Over time whatever was causing the code to set could have gotten progressively worse to the point where you could actually feel it. When you had the clutch replaced, did you have the original flywheel resurfaced or did you put an after market flywheel on?
Ok, they don't usually come in a clutch kit so we'll assume that its still the original. A few factors could cause your code to pop up, all of which are tough to single out without swapping/replacing parts. The one thing i would look at first is where the ram air intake is positioned. I have seen where they will sit in the path of the cooling fans coming on and the quick burst of hot air will cause havoc with the computer, and this might have been repositioned when the clutch was replaced. Usually coils and wires will cause individual cylinder codes to set, same as with injectors, but the MAF sensor is common to all. Check that out and let me know if that helps. Also, do you know if it does it only when hot above 70 mph, or can you take it out cold and it will do it as well?
Another TSB with these cars is tsb-06-13-004, which describes all of your concerns as well. If the vehicle is above 167 degrees, over 60 mph, rpm over 2500 and engine load is less than 80%. Unfortunately the repair isn't cheap but is also a known problem with the EVO's, and that is to replace the input shaft in the transmission because it sees the splines on the 5th gear moving and it sees this as a misfire. In order to repair it you'll need the following 3 parts: Input shaft - MN107628, Input 5th gear - MN107624, and the input shaft seal should also be replaced which is MD746516.
EVO's only have a 5 year, 60,000 mile powertrain warranty, so by mileage yes, time no. Mitsubishi is very strict with them and having modifications done to them, so if it was stock you might have a chance with a district rep helping you out with it, but they definitely won't since its been modified and probably not since its out by a few years as well.