As far as I know Exporter's import method is executed at compile time. Strange thing here is that First did not exported any of its methods before using Second. So, in the second compilation of Second, by the time we are at "use First qw(first_method);", First's EXPORT_OK is empty, therefore the compilation should fail...

Yes, import is executed at compile time, but after the respective module has been compiled in its entirety — not somewhere in the middle of use-ing one of its dependencies (after all, First.pm might have defined its own import method further down, which would of course have to be compiled before it can be called...). So, at the point when import is called, @EXPORT_OK is already set up; therefore it's no surprise you're not getting the '"first_method" is not exported by...' error message.

If you add your own import method to First.pm, e.g. like this

...
# Exporting methods
use Exporter;
our @EXPORT_OK = qw(first_method);
our @ISA = qw(Exporter);

sub import {
    print "First::import(): \@EXPORT_OK = @EXPORT_OK, args = @_\n";

    goto &{Exporter::import};
    # alternatively, if you dislike hardcoding stuff:
    # if (my $super_import = __PACKAGE__->can("SUPER::import") ) {
    #     goto &{$super_import};
    # }
}
...
[download]

you'll see that it is being called rather late.  Output of perl -wc Second.pm:

Start compiling Second
Before using First in Second
Start compiling First
Before using Second in First
Start compiling Second
Before using First in Second
After using First in Second
Just used Second in Data
Methods are exported from First
First::import(): @EXPORT_OK = first_method, args = First first_method
After using First in Second
Subroutine second_method redefined at Second.pm line 22.
Second.pm syntax OK
[download]