Which version of windows are you using?
Is your windows system 32 or 64 bit?
It may be that PhotoDeluxe 4 just won't work on newer windows operating systems.
Have you tried right clicking on the PhotoDeluxe 4 shortcut selecting Properties and trying a Compatibility mode such as windows xp or windows 2000 under the Compatibility tab?
I believe the reason for that message is the default memory usage for PhotoDeluxe is set to 75% and it probably needs to be set to 50% by editing the PD.INI file.