I would be inclined to appeal, though I say that without enough awareness of the associated costs, so I can't actually recommend one way or the other whether you should appeal or reapply.
The refusal strikes me as scandalous. Consider the guidance for evaluating your application under which the entry clearance operator was working (emphasis added):
EUN2.10 What if I suspect a marriage / civil partnership of convenience?
The definition of ‘spouse’ and ‘civil partner’ in the EEA Regulations does not include someone who has entered into a marriage / civil partnership of convenience.
When a marriage / civil partnership of convenience is suspected, the burden of proof is high and rests with the ECO. However, in these cases the ECO is entitled to interview the applicant. Factors to consider include:
- an adverse immigration history;
- doubts about the validity of documentation;
- application follows soon after the marriage / civil partnership;
- no previous evidence of the relationship.
The ECO should not consider the following cases as marriages / civil partnerships of convenience where:
- there is a child of the relationship;
- there is evidence to suggest cohabitation.
The key phrase here is the burden of proof is high and rests with the ECO. In fact, the ECO has responded as if the burden of proof were on you ("reasonable to expect ... no evidence provided to demonstrate").
The fact that your application came a few months after your marriage is, I suppose, sufficient to invoke the third "factor to consider," but the ECO should have made some effort to develop evidence to satisfy his or her burden of proof, and did not.
Have the two of you ever lived together? If so, and if either you reapply or your appeal raises the question of additional evidence, I would skip the chat histories and phone logs, and instead rely on the last bullet point, which should be much easier and quicker to show. In addition, it will be a more reliable defense against any suggestion that yours is a marriage of convenience.
For an EU perspective on the question, see https://eumovement.wordpress.com/2014/10/16/eu-free-movement-handbook-on-alleged-marriages-of-convenience/. A selection (emphasis removed):
Burden of proof is on the national authorities to prove abuse
Married couples cannot be obliged or required, as a rule, to present evidence that their marriage is not abusive.
EU citizens and their family members enjoy the benefit of assumption, meaning that they do not need to provide evidence that their marriage is genuine. To require this would go beyond the requirement to present proof that their marriage is valid.
This reflects the principle of law that the person who lays charges has to prove the charges (‘semper necessitas probandi incumbit ei qui agit‘).
The burden of proof clearly rests on the national authorities who suspect that a non-EU national has entered into a marriage of convenience with an EU citizen for the sole purpose of being granted an EU right to free movement to prove that the marriage is of convenience.
Here is a story of a successful appeal, in which the court awarded the cost of the appeal to the appellant: http://www.immigrationboards.com/eea-route-applications/won-vs-marriage-of-convenience-details-inside-now-t124572.html. A selection:
Applied in June for EEA family permit.
Rejected - marriage of convenience
Appealed and Reapplied
2nd application Rejected in July - same reason with very aggressive and bad wording
Today i got Letter from HM court and Tribunal
They decided in my favor and gave my 80 Euro back
If you read down a bit, you can see the (very poorly scanned) text of the appeal decision. That makes it clear that the ECO has a burden to prove a reasonable suspicion that the marriage is one of convenience, at which point the burden shifts to the visa application to prove that it is not. I do not know whether the amount of time between your marriage and the application is sufficient evidence of reasonable suspicion.