Place your message on a conventional, NASA-type space probe.
Launch it into a long, cometary orbit, calculated to return to Earth in 5 billion years. The endless void of space is a fine preservative. Ordinary steel should do the trick.
And, hey! Say “Hi!” to your gret-great-etcerta-etcetera grandaughter for me. That’s one hot babe. The last time I saw her I… oops. Mr. Wells & Messr. Verne asked me not to talk about that part.
Just check to see if she’s pregnant, OK?
OK.