Eager evaluation is, in fact, a side effect! Think about it: eager evaluation means that you KNOW function arguments get evaluated BEFORE the function gets called. So, a PURE functional language must be a lazy language (more technically, "non-strict," and sorry for the confusing lingo: STRICT means non-lazy).
So we know that F# isn't purely functional because it's not lazy. That's ok, the monad style in F# / C# / VB is still very useful for compositional designs, even if the languages are not "pure." Some people call F# and ML and OCaml and Scheme, etc., "almost functional." 80% of the time, there won't be any difference between pure-functional and almost-functional. But you have to be careful at the fringes.
You can build lazy libraries and such and get all the way to pure functional if you need it. Heck, you can implement Haskell in F#, so there
There's lots more to say about this, so stay tuned.