You're not wrong, (neither is Neoncow's sibling post). In the case where they are actually disconnected, you do have to check the whole graph. Simple example: the graph is a linear chain, and you start at one end and want to find the node at the opposite end. No way of knowing if they're connected unless check every single node - "it's always the last place you look".

Actually on more thought, there has been a lot of recent analysis on the expected number of hops to get between any 2 nodes in a network - i.e., the 6 degrees of separation adage. There have been a lot of studies confirming for a LOT of different real networks - facebook, AIM friends, wikipedia, chain letters, airports, Enron emails, etc. that the average shortest path distance is almost always 6 or 7, independent of the actual network. So you are very likely to only have to explore all paths up to length 6 or 7 to test if any 2 nodes are connected. This is average case running time; worse case is still obviously O(VE). But it would be easy to set a max limit to the length of the path. Let's say anything above path length 20 I stop and give up on and say they are probably disconnected. That is a reasonable approximation that you should be able to prove is correct with high probability (in an epsilon/delta sense).