Benedick a while back.  Both this things imply a romantic history between the two characters.

It is difficult to determine just how genuinely concerned she is about is welfare for there is some indication they had a relationship in the past and she remains angry and hurt by its outcome. That is not to say she wishes him ill, that she wishes he had come to harm in battle, for that is not the case. However, when she says "He is sooner caught than the pestilence" and then later in speaking to him "You always end with a jade's trick.  I know you of old" (85, 143), she indicates they do have a past that left resentment in her heart.

The reason why Beatrice asks the messenger if Benedick has returned home from the wars is that they have a love-hate relationship. They are the sort of people who absolutely love to hate each other. One reason they love to hate each other is that they are very similar people in intellect and love to challenge each other's wits. It is possible to deduce that another reason why they hate each other is that there is some sexual tension. It is possible that Benedick tricked Beatrice into falling for him before but then broke her heart.

We see the first clue that Beatrice may have been fond of Benedick in the first scene. After asking about Benedick, Beatrice next relays a strange story about Benedick in relation to Cupid, the Roman god of love. She says that Benedick challenged Cupid in archery but that Leonato's jester answered Cupid's challenge instead (I.i.32-35). Her meaning is unclear in these lines but she seems to be saying that Benedick isn't any good at either fighting in battle or at pursuing love. Her references to Cupid and love may indicate that she had feelings for Benedick but that he sabotaged these feelings somehow.

A second clue we see that may allude to the fact that she had prior feelings for Benedick is seen at the masquerade ball. Benedick approaches her in a mask and she calls Benedick a fool, pretending not to know that it is Benedick behind the mask. Benedick then cries on the princes shoulder about her insult, and Don Pedro says to Beatrice, "[Y]ou have lost the heart of Signor Benedick" (II.i.243-244). Beatrice relays the very enlightening information that Benedick once "lent" her his heart and she "gave him use for it" (245-246). This line could indicate that Benedick once tried to court her and she reciprocated his feelings. But she then says, "Marry, once before he won it of me with false dice; therefore your Grace may well say I have lost it" (246-248). This line can be interpreted to mean that he won her heart through some sort of insincere trick. If Beatrice really does feel tricked by Benedick with respect to love, then this line can certainly explain their love-hate relationship, their battle of wits, and why she asks about Benedick in the first scene.