The key legislation here is the Leahy-Smith America Invents Act of 2011 (AIA) that makes some changes in the definition of prior art and in the types of post-grant review proceedings. The changes to prior art definitions will only apply to patent applications with an effective filing date of on or after March 16, 2013. Thus, the old law would apply to a patent issued in the 2000's. One exception, however, is that a new interpretation of a statute by a court is normally applied retroactively. Thus, when the Supreme Court re-interpreted the obviousness doctrine in 2007, that change applied equally to patents that had already issued. See KSR v. Teleflex. Because of KSR, it should be easier to invalidate the patent than it was back in 2003 -- even though the same legislation applies.
The post below does not answer your edited question, but it does provide some important information on mechanisms for challenging patents.
There are several ways to challenge the validity or enforceability of a US patent. For the particular case introduced above (patent filed and issued in the 2000's), the three available mechanisms appear to be (1) federal court challenge; (2) ex parte reexamination; and (3) inter partes review.
What I'm going to do here is list all the ways that patents can be challenged. The following is a listing of mechanisms for opposing US patents (and pending applications). Each mechanism has a number of intricacies that are not mentioned here. All of the post-grant options are expensive.
- Federal Court: Any patent can be challenged in federal court by filing a declaratory judgment (DJ) action. Before you can file DJ action, you must somehow be threatened by the patent. Otherwise you have no standing to file and the lawsuit will be summarily dismissed.
- Ex Parte Reexamination: Any issued patent (new or old, and including design patents) can be challenged by filing a request for ex parte reexamination at the USPTO. The ex parte reexamination request must raise a substantial new question of patentability that is based only upon prior art patents and printed publications. Ex Parte Reexamination cannot be used to directly challenge other non-prior art questions such as patentable subject matter, indefiniteness, utility, or inequitable conduct. Anyone can file an ex parte reexamination request.
- Inter Partes Reexamination: Inter partes reexamination is no longer available. Thus, unless you filed a request before September 16, 2012, you have lost your shot. However, inter partes reexamination is being replaced by the combination of inter partes reviews and post grant reviews.
- Inter Partes Review: Any issued patent (new and old) can be challenged with an inter partes review. EXCEPT that the patent must be at least 9-months old. Thus as of today (October 1, 2012), the only patents available for inter partes review were those issued before February 1, 2012.
- Post Grant Review: The post grant review system has not been implemented yet because the only impacted patents are those with an effective filing date of on or after March 16, 2013. Because the USPTO normally takes a few years to issue patents, it may well be 2015 before we see the first post grant review filing. Once a patent issues, the post grant review must be requested within the first 9-months following issuance. The process for post grant reviews and inter partes reviews are quite similar. The difference is only that a post grant review can challenge a broader scope of patentability questions that might have nothing to do with prior art.
- Transitional Covered Business Method Review: The new business method review applies to all business method patents regardless of filing or issue date. However, it can only be used against patents that claim financial services related business method inventions that do not include technological inventions. The review is termed "transitional" because it has a sunset provision. No new TPCBM requests will be accepted on or after September 16, 2020.
- Interference Proceedings: Patent with an effective filing date of before March 16, 2013 will still fall under the old first-to-invent rules. Thus, those applications can still be subject to an 'interference proceeding' where the USPTO attempts to figure out who is the first inventor (or who can prove that they were the first inventor). To challenge another application/patent in this manner, you must file your own patent application within one year of the opposing entity's patent issuance. I believe that to be eligible for an interference that you must also file your application before the March 16, 2013 date discussed above.
- Derivation Proceeding: Derivation proceedings are remaining as a vestige of interference practice. If someone else used your work as the basis for their patent application, then you can file your own derivation petition that asks the USPTO to axe their application. A petition for a derivation proceeding must be filed within one-year of the first publication of the offending application. Despite the seemingly broad wording of "derivation," these cases are limited only to instances where the original invention is identical or substantially identical to the application being opposed. If you miss this deadline, patent ownership rights can still be challenged in court.
- Pre-Issuance Submissions: As discussed here, prior art can be submitted for consideration at the USPTO while an application is still pending. The deadline for this submission is fairly tight. However, this is an attractive option if you meet the timeline because the submission is free.
- Three other post-grant reviews - Reissues, Supplemental Examination, and Corrections are only available to the patent owner.
The USPTO has provided a fairly comprehensive guide to some of these changes at the following link.