Here's a puzzle I created and posted to rec.puzzles in October 1991:

A number theorist set his car's odometer to zero and then went for a drive along the roads shown below, starting and ending in his home town. He noticed that his odometer reading was a prime number each time he entered a town. Where did he live and how far did he drive?

(Notes to avoid trick solutions: Every town is at an intersection of roads and every such intersection has a town. Distances on the map are in miles and are exact. The odometer measures miles and is accurate. The driver didn't reset his odometer at any time after he started. He never turned around outside of a town, but he did sometimes leave a town by the road on which he arrived. He didn't add extra distance by driving within a town or raising his car off the ground and spinning his wheels or getting out of the car while someone else drove it. He didn't subtract distance by driving backward. He stayed on the roads shown here at all times. Etc.)

                   A-----------B
                  /|\    2     |\
                 / | \         | \
                /  |  \        |  \
               /   |   \       |   \
              /    |    \      |    \
             /     |     \10   |14   \
            /     8|      \    |      \
           /       |       \   |       \
          /5       |        \  |      17\
         /         |         \ |         \
        /          |    12    \|          \
       /           C-----------D           \
      /            |\         /             \
     /             | \       /               \
    /             3|  \10   /4                \
   /               |   \   /                   \
  /          6     |    \ /                8    \
 E-----F-----------G     H           I-----------J
 |  2   \          |     |          /|          /|
 |       \         |     |         / |         / |
 |        \        |     |       4/  |6     10/  |
 |         \       |     |       /   |       /   |
 |          \      |     |      /    | 12   /    |
 |6         6\     |4    |     K     L-----M    6|
 |            \    |     |     |\    |     |     |
 |             \   |     |     | \   |     |     |
 |              \  |    8|   12|  \  |8    |8    |
 |               \ |     |     | 12\ |     |     |
 |        2       \|     |     |    \|     | 12  |
 N-----------------O     |     P     Q-----R-----S
  \                |     |    /|       10       /
   \               |     |  6/ |               /
    \              |     |  /  |              /
     \             |     | /   |             /
      \            |     |/    |            /
       \           |     T     |4          /
        \          |      \    |          /
         \         |       \   |         /
          \4     12|      14\  |      13/
           \       |         \ |       /
            \      |          \|      /
             \     |           U     /
              \    |           |    /
               \   |           |   /
                \  |         10|  /
                 \ |           | /
                  \|     2     |/
                   V-----------W

Click here for a different kind of prime maze.