Normally, fights/enemies should have constant strength. Some things though, for sure are scripted - for example Double and Future fights. This may be the case with the cursed treasure, but I won't bet on this
And in my game I did manage to do it as a first quest on the Freedom islands. I had pretty strong children from the Zombie wife tho. (+5 def, +3 att, +20% def, +20% att) and was like lvl 11 at that time ...