There is a letter from Fermat to Mersenne, sent in September 1636, where Fermat proposes such problem:

> $3^o$. Invenire duo quadratoquadratos quorum summa aequetur
> quadratoquadrato, aut duos cubos
> quorum summa sit cubus.

or "Find two fourth powers, whose sum is the fourth power or two cubes, whose sum is a cube."

So, Fermat definitely had thought about this problem in 1636. The letter could be found [here][1].


  [1]: http://www.archive.org/details/oeuvresdefermat942ferm