Sorry for all the colors - I am copying from my spreadsheet. There have been improvements in the EGR valve. My recommendation (if you are going to keep the EGR system) is to replace it. If you want to clean it, here is more to read ..........

<TABLE style="WIDTH: 660pt; BORDER-COLLAPSE: collapse" cellSpacing=0 cellPadding=0 width=880 border=0 x:str><COLGROUP><COL style="WIDTH: 660pt; mso-width-source: userset; mso-width-alt: 32182" width=880><TBODY><TR style="HEIGHT: 12.75pt" height=17><TD class=xl24 style="BORDER-RIGHT: #d4d0c8; BORDER-TOP: windowtext 1pt solid; BORDER-LEFT: windowtext 1pt solid; WIDTH: 660pt; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 12.75pt; BACKGROUND-COLOR: silver" width=880 height=17>REMOVE EGR Valve
</TD></TR><TR style="HEIGHT: 12.75pt" height=17><TD class=xl25 style="BORDER-RIGHT: #d4d0c8; BORDER-TOP: windowtext; BORDER-LEFT: windowtext 1pt solid; WIDTH: 660pt; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 12.75pt; BACKGROUND-COLOR: silver" width=880 height=17></TD></TR><TR style="HEIGHT: 67.5pt" height=90><TD class=xl26 style="BORDER-RIGHT: #d4d0c8; BORDER-TOP: windowtext; BORDER-LEFT: windowtext 1pt solid; WIDTH: 660pt; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 67.5pt; BACKGROUND-COLOR: silver" width=880 height=90>Clean it - Use Carburetor cleaner, not brake cleaner - keep the fluid out of the weep holes. Use new O-Rings (kit number is 3C3Z-9P455-AB).
ALSO: Clean EBP tube (vehicles built before 9/23/03 have the EBP sensor taken out of the computer control strategy), Also clean MAP sensor hose and manifold opening.
To remove: take the 2 8mm bolts out, spin the valve by hand, and use two lady fingers or heel bars depending where you live (1 under each tab) and pop it right out.
When you go to install the valve it is normal for the valve not to go all the way in. Push it as far as you can and use the bolts to suck it in.</TD></TR><TR style="HEIGHT: 22.5pt" height=30><TD class=xl26 style="BORDER-RIGHT: #d4d0c8; BORDER-TOP: windowtext; BORDER-LEFT: windowtext 1pt solid; WIDTH: 660pt; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 22.5pt; BACKGROUND-COLOR: silver" width=880 height=30>Carb Cleaner recommendation (see link below and refer to old TSB 06-19-6): Note 07-21-9 supercedes 06-19-6 </TD></TR><TR style="HEIGHT: 12.75pt" height=17><TD class=xl27 style="BORDER-RIGHT: #d4d0c8; BORDER-TOP: #d4d0c8; BORDER-LEFT: #d4d0c8; BORDER-BOTTOM: #d4d0c8; HEIGHT: 12.75pt; BACKGROUND-COLOR: silver" height=17>http://www.forddoctorsdts.com/articles/article-06-12.php</TD></TR><TR style="HEIGHT: 13.5pt" height=18><TD class=xl27 style="BORDER-RIGHT: #d4d0c8; BORDER-TOP: #d4d0c8; BORDER-LEFT: #d4d0c8; BORDER-BOTTOM: #d4d0c8; HEIGHT: 13.5pt; BACKGROUND-COLOR: silver" height=18>"http://www dot powerstroke dot org/forum/general-6-0l-discussion/63592-6-0l-egr-maintenance-cleaning-write-up dot html"</TD></TR><TR style="HEIGHT: 15.75pt" height=21><TD class=xl29 style="BORDER-RIGHT: windowtext 1pt solid; BORDER-TOP: windowtext 1pt solid; BORDER-LEFT: windowtext 1pt solid; BORDER-BOTTOM: #d4d0c8; HEIGHT: 15.75pt; BACKGROUND-COLOR: fuchsia" height=21>At about 1:40 in the Ford Presentation below, they state NOT to use Breake Cleaner</TD></TR><TR style="HEIGHT: 13.5pt" height=18><TD class=xl28 style="BORDER-RIGHT: windowtext 1pt solid; BORDER-TOP: #d4d0c8; BORDER-LEFT: windowtext 1pt solid; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 13.5pt; BACKGROUND-COLOR: fuchsia" height=18>mms://multimedia.ford.com/seopts/Tech_31_250k.wmv</TD></TR></TBODY></TABLE>

<TABLE style="WIDTH: 660pt; BORDER-COLLAPSE: collapse" cellSpacing=0 cellPadding=0 width=880 border=0 x:str><COLGROUP><COL style="WIDTH: 660pt; mso-width-source: userset; mso-width-alt: 32182" width=880><TBODY><TR style="HEIGHT: 12.75pt" height=17><TD class=xl24 style="BORDER-RIGHT: windowtext 0.5pt solid; BORDER-TOP: windowtext 0.5pt solid; BORDER-LEFT: windowtext 1pt solid; WIDTH: 660pt; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 12.75pt; BACKGROUND-COLOR: silver" width=880 height=17>EGR O-ring kit number is 3C3Z-9P455-AB or International # 1840778C92; EGR bolts are torqued to 13 Nm</TD></TR><TR style="HEIGHT: 33.75pt" height=45><TD class=xl24 style="BORDER-RIGHT: windowtext 0.5pt solid; BORDER-TOP: windowtext; BORDER-LEFT: windowtext 1pt solid; WIDTH: 660pt; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 33.75pt; BACKGROUND-COLOR: silver" width=880 height=45>2003/2004 Service EGR valves: Ford Part Number 4C3Z-9F452-A and International #1846491C91 (PN on valve 4276L); 2005/2006 Service EGR valves: Ford Part Number 5C3Z-9F452-AA International # 1846490C91 (PN on valve 4043H)
The original valve numbers were: 2003/2004 3C34-9F452-AC (PN on valve 03191) AND 2005/2006 5C34-9F452-AA (PN on valve 4043H)</TD></TR><TR style="HEIGHT: 13.5pt" height=18><TD class=xl25 style="BORDER-RIGHT: windowtext 0.5pt solid; BORDER-TOP: windowtext; BORDER-LEFT: windowtext 1pt solid; WIDTH: 660pt; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 13.5pt; BACKGROUND-COLOR: silver" width=880 height=18>The new (good) EGR valves have a blue dot and a pink dot on the top of the actuator.</TD></TR></TBODY></TABLE>

Also - clean your EBP tube and MAP sensor hose (if applicable):
<TABLE style="WIDTH: 660pt; BORDER-COLLAPSE: collapse" cellSpacing=0 cellPadding=0 width=880 border=0 x:str><COLGROUP><COL style="WIDTH: 660pt; mso-width-source: userset; mso-width-alt: 32182" width=880><TBODY><TR style="HEIGHT: 12.75pt" height=17><TD class=xl24 style="BORDER-RIGHT: windowtext 0.5pt solid; BORDER-TOP: #d4d0c8; BORDER-LEFT: windowtext 1pt solid; WIDTH: 660pt; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 12.75pt; BACKGROUND-COLOR: yellow" width=880 height=17>http://www.thedieselstop.com/forums/f24/ebp-pipe-location-cleaning-advice-146925/</TD></TR></TBODY></TABLE>
<TABLE style="WIDTH: 162pt; BORDER-COLLAPSE: collapse" cellSpacing=0 cellPadding=0 width=216 border=0 x:str><COLGROUP><COL style="WIDTH: 162pt; mso-width-source: userset; mso-width-alt: 7899" width=216><TBODY><TR style="HEIGHT: 13.5pt" height=18><TD class=xl25 style="BORDER-RIGHT: windowtext 1pt solid; BORDER-TOP: windowtext 0.5pt solid; BORDER-LEFT: windowtext 0.5pt solid; WIDTH: 162pt; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 13.5pt; BACKGROUND-COLOR: silver" width=216 height=18>EBP Exhaust Back Pressure</TD></TR><TR style="HEIGHT: 12.75pt" height=17><TD class=xl24 style="BORDER-RIGHT: windowtext 1pt solid; BORDER-TOP: windowtext; BORDER-LEFT: windowtext 0.5pt solid; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 12.75pt; BACKGROUND-COLOR: silver" height=17>http://dan.prxy.org/Truck/6L_bible_h.../Page_058.html</TD></TR><TR style="HEIGHT: 12.75pt" height=17><TD class=xl24 style="BORDER-RIGHT: windowtext 1pt solid; BORDER-TOP: windowtext; BORDER-LEFT: windowtext 0.5pt solid; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 12.75pt; BACKGROUND-COLOR: silver" height=17>http://dan.prxy.org/Truck/6L_bible_h.../Page_009.html</TD></TR></TBODY></TABLE>
<TABLE style="WIDTH: 162pt; BORDER-COLLAPSE: collapse" cellSpacing=0 cellPadding=0 width=216 border=0 x:str><COLGROUP><COL style="WIDTH: 162pt; mso-width-source: userset; mso-width-alt: 7899" width=216><TBODY><TR style="HEIGHT: 45pt" height=60><TD class=xl24 style="BORDER-RIGHT: windowtext 1pt solid; BORDER-TOP: #d4d0c8; BORDER-LEFT: #d4d0c8; WIDTH: 162pt; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 45pt; BACKGROUND-COLOR: silver" width=216 height=60>MAP - Manifold Absolute Pressure</TD></TR><TR style="HEIGHT: 12.75pt" height=17><TD class=xl25 style="BORDER-RIGHT: windowtext 1pt solid; BORDER-TOP: windowtext; BORDER-LEFT: #d4d0c8; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 12.75pt; BACKGROUND-COLOR: silver" height=17>The MAP port is on the intake manifold. The hose comes off of that port.</TD></TR><TR style="HEIGHT: 12.75pt" height=17><TD class=xl26 style="BORDER-RIGHT: windowtext 1pt solid; BORDER-TOP: windowtext; BORDER-LEFT: #d4d0c8; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 12.75pt; BACKGROUND-COLOR: silver" height=17>http://dan.prxy.org/Truck/6L_bible_h.../Page_038.html</TD></TR><TR style="HEIGHT: 12.75pt" height=17><TD class=xl26 style="BORDER-RIGHT: windowtext 1pt solid; BORDER-TOP: windowtext; BORDER-LEFT: #d4d0c8; BORDER-BOTTOM: windowtext 0.5pt solid; HEIGHT: 12.75pt; BACKGROUND-COLOR: silver" height=17>http://dan.prxy.org/Truck/6L_bible_h.../Page_063.html</TD></TR></TBODY></TABLE>

Let us know what the valve looked like. You can tell some things from the appearance.