With Avast having tens of millions of users I would think that these famous people would offer to do it for free given all the free advertising that it would give them.
Well, I can imagine such people may have quite a few similar offers... and possibly a lot of other things to do - than spend time in a recording studio. However, I'd say the main problem is to get through to these people - over their agents.
For example the voice message could say: Hi this is so and so and your virus definitions have been updated.
Personally, I don't like this "Hi this is..." (I believe we actually have something similar in one of the Polish themes). I mean, might be funny at first, but if you hear it every day, possibly even twice a day...
(just my personal opinion though)
Nothing to get these people into a recording studio. They are always around one. In fact a lot of them have studios in their homes. So all they have to do is read a few lines for Avast while they are in the studio and finished. All of maybe a minute tops.
As far as what they say I hear ya. I leave that up to the Avast team to figure out. However, no problem getting through to them. Start with a famous person from the Czech Republic that one of the people in Avast knows. Its not like The Czech Republic is that a big a country where no one in Avast would not know one of these people. Start with that one or two countryman/countrywomen and see how it goes. If people like it then I am sure that the famous people who someone at Avast knows, knows people that are famous that don't live in the Czech Republic. So on an so forth.
I agree at least initially it would be difficult to go through agents but through personal relationships it might just work enough to get the ball rolling.
How exactly it would be done I leave that up to the Avast team.