I don't have any example in mind at the moment, but I'll try clearing your doubts.
Pathfinding algorithms work on graph structures (connection of nodes). A grid is an example of a graph, but it's not the only graph structure available for pathfinding. Basically, any kind of "set of nodes" will do.
If you don't have a tiled map, don't worry, you can still have nodes where you desire. A common thing to do is create a navigation mesh (nav mesh), a human-designed or procedurally-generated graph that places nodes in parts of your map you can walk into.
The above picture is a navigation mesh from World of Warcraft. The green nodes are used for pathfinding, and the polygons created by connecting those nodes sample the walkable space. This should clarify questions 1 and 3.
Another common practice is creating many grids on top of your current level architecture, every one more precise than the previous one, in order to speed up pathfinding.
Performance can be an issue, but you can be smart about it. If you don't need every single actor to find its own path, you could use influence maps or breadth-first search to crate a global map the actors will follow.
Check this video out: http://www.youtube.com/watch?v=DusL7kXSJlc
The goal (in this case the player), generates an influence map around him, and what the enemies do is simply move from areas with less influence to areas with more influence, no pathfinding involved on their part. You can generate multiple influence maps if you have more goals (for example, more "factions" battling each other in a RTS).
Pathfinding is a complex subject, but there are many resources you can find by googling.
Let me know if you still have doubts.