Every SPQuery's query should have
<View><Query> query... </Query></View>
Sometimes I have to put without those tags to get it work and some times I have to put it with the tags, why is this?
If you read these two pages, you'll see that the two different properties require different structure.
You'll see that ViewXML is the full Query, thus needs the View and Query tags, whereas the Query property is just the "filter" part of the query. SPQuery internally builds up the View and Query elements around the Query property to produce the full CAML Query which appears as the ViewXML property.