Note: read the following real expert opinions later on before doing anything I suggest. It seems that the Bink video player is the likely culprit.
I have had some problems running more recent versions of Direct X with early patches of EU2. You can try installing Direct X 8.0. If you have played HoI2 or CK, you probably have Direct X 9.x. Also, if the game is failing at startup, it is likely the Bink video that is failing. You can rename the AVI folder.
Possibly your display driver is the problem. If you are running in a display mode other than 640x480, EU2 will temporarily switch to 640x480 on startup even if the settings are made for higher resolution. That could cause a problem in the switch. Try setting your Windows and setting resolutions to 640x480. Color depth may instead be the reason I have experienced some problems.
Oh, and there is a CD check in versions earlier than 1.05. That may be a problem if your CD is not present in the lowest CD drive letter or in the CD drive that the game was installed from. That is just a total guess.
Upgrading to version 1.08 or later is probably the best option since there have been many improvements that you would probably like to have anyway. There is a
patch archive that has a number of patches split into floppy-sized chunks. There should be no limitations on your ability to download a patch suitable to your needs. Personally, I prefer the March 2, 2004 beta of 1.07. The version may still have a problem with Direct X though.