If the celebrity isn't following you, the message you'll send them will drop in the message requests box without a notice, which, honestly, anyone rarely checks.