As a general rule, there has to be at least 2 tiles between your troops and their borders. Sometimes one will suffice. But it's based on line-of-sight. The number of units near their borders that they're aware of is the determining factor, so you can get unlucky. If there's a hill or forest between you and their borders, and the tile in their borders is flatland, they can't see you. If the tile is on a hill, it can see farther sometimes. If your unit is on a hill, it can be seen from farther away. It's definitely tricky, but you can avoid it to some degree. Just be ready to declare war if they do accuse you.
What *REALLY* drives me crazy is when I'm moving troops towards someone else and they ask that. Now I can't attack them for 30+ turns without a rep hit.