You must update to each of the major versions as covered in the release notes:
7.3 E504xxx > 7.3 E506
7.3 E506 > 7.3 E605
7.3 E605 > 7.3 E605P04
You supposedly can skip the patches on the intermediate steps (Pxx)
If you are on vmware or similar then I'd suggest a snapshot after each upgrade step, in case something happens - you don't need to start over. Sometimes if there is an issue with a full step up, applying a patch in between might help.
Figure this will take 2-3 hrs for each step depending. If you are running other modules, you may want to upgrade the major versions of those in sync along with - don't know if its required but that's how I would go.
Maybe others have a different take on that?