I'm not an expert on it, so please don't take my comments other than as comments.

I think there is a problem with how you mix @EXPORT with the other code that should do the redefine, as it makes your 'old' module::function to become main::function.

main is the third player in the game, that you seem to ignore. If you use the test as

use module;
use redefine;

module::function();
[download]

it will work as wanted, regardless in which order you 'use' the moduls. You might want eighter to not export, or maybe to redefine main::function instead of module::function.