The ‘strangeness’ is perhaps not so obvious with a very ‘light’ (brief) adjunct like this; but try it with a heavier phrase:
Andre ate with enormous relish all the biscuits.
Andre ate without stopping to thank his hostess all the biscuits.
The important thing is that the connection between the verb and its direct object should not be obscured. Constituents (primary syntactical components of a sentence: Subject, Verb, Objects) should be in the ‘foreground’, and adjuncts should be ‘backgrounded’. (And by the same token, your sentence should be constructed in such a manner that the pieces you want to emphasize are realized as constituents, not adjuncts.)
So constructions like this are a little more acceptable if the adjunct is parenthesized by enclosing it in commas, dashes, or parentheses:
Andre ate, greedily, all the biscuits.
But even this should be avoided unless you have some strong reason for intruding the adjunct into an abnormal position, and unless you have some means of bringing the direct object back into the foreground after the digression:
Andre ate, with truly repulsive greediness, every single biscuit!
Here I have created a climax: the adjunct is intruded so that I have a little ‘ladder’ by which I mount to my sense of outrage at the top.