If it were me, I would say that under the effects of this spell combined with invisibility there would have to be some environmental condition for anyone to even notice something strange, such as snow, tall grass or standing water. In that case, your character would create a "hole" in the environment. If you are using this spell and are invisible, it is rather strongly implied that you are intending to be stealthy, therefore, in order for that "hole" to be noticed by others, your stealth check would need to be defeated. Even then, that would only make the strange feature noticeable, not necessarily be obvious that there is a invisible character there.
In addition, if it were something like snow, as you moved, the snow would magically refill itself leaving no trace of your passage and nothing for anyone to track. Every time your character moved, a new stealth check would be needed to notice the new location. After a few failed stealth checks, a highly intelligent NPC might make a check to understand what is happening. The reason I say it is possible to notice your character at all, even in those specific environmental conditions, is because it does not say leaving no trace of your presence, it says no trace of your passage. In the condition of riding fast across a desert, the hoof prints of where your horse currently is pressing into the sand would be so small and disappear so quickly as the horse moved, that it would effectively be impossible for anyone to even notice them.
In the end though, your GM must make the ruling and you must abide by it. As was mentioned, there may be some story reason for this, however it would benefit the groups morale for the GM to find some other way to introduce their narrative point, such as someone in the tavern overhearing your plan, or they used magic to track you, which is an obvious way around it.
That said, if my group went to all that trouble and had that much forethought to defeat detection and tracking, I would abandon my plot device and come up with something new. They earned that victory. In addition I would find some way of letting my players find out about what they managed to avoid by being inventive. Ingenuity should be rewarded.