Another problem with this strategy is that it generally requires solving the halting problem: you can only know whether a program "does a given task" when you know whether it halts or not.
The definition of enumeration commonly used in computability does not require that you know when you are done enumerating.
Sorry, but this is a non-sequitur. In order to find (by enumeration) the shortest program producing a certain output, you absolutely do need to know when you're done, and thus you do need to solve the halting problem.
The idea behind most enumeration algorithms looks like this:
machines = {}
next_program = 0
loop forever:
machines.insert(new_turing_machine(next_program))
next_program++
for machine in machines:
machine.step()
if machine.halted():
machines.remove(machine)
if machine has output we want:
yield machine