Proposed enhancement to strlen_P():
#define my_strlen_P(s) \ __builtin_choose_expr( \ __builtin_constant_p(__builtin_strlen(s)), \ __builtin_strlen(s), \ strlen_P(s) \ )
This should avoid calling the strlen_P function if the string size is known to the compiler beforehand (i.e. if the parameter to strlen_P is not a changing pointer). This is in fact how strlen() works anyway (through a mechanism in __builtin_strlen() hidden to the user).
Of course, the real change would involve also to rename the current library function strlen_P() to say __strlen_P() and then this macro would be part of pgmspace.h, calling __strlen_P() in cases where appropriate.