I set the environment variable on the command line first and then ran my test. The value used by mylib is the one that was set on the command line and not the one from within Perl

Yes, I see the same behaviour (on Win32, btw).
I even tried setting the environment variable at the very beginning of the perl script, inside a BEGIN{} block ... but the external library still doesn't see that value.

I'm wondering whether a dynamic (shared) library might see the new value, but I don't think it would. (You could try that if you think it's worth a shot - my 'libmylib' was a static library.)

Only other thing I can think of is that your library needs a 'setenv' implementation, which you can then call from perl via an Inline::C wrapper whenever you alter an environment variable.

Cheers,
Rob