A* Pathfinding Bug: Dictionary Key Not Found Exception

Hey, I'm making a tower defense game which of course involves pathfinding and waves of enemies being generated. I've encountered a really strange bug however.

Basically, when a wave is generated each enemy generated has an enemy script which calls the FindPathTo(Vector2 endGoal) method on the Pathfinding script.

 public List<Tile> FindPathTo(Vector2 target){
     //key node visited, value: node you came from to arrive
     Dictionary<Tile, Tile> cameFrom =  new Dictionary<Tile, Tile>();
     //nodes to visit
     List<Tile> frontier = new List<Tile>();
     List<Tile> path = new List<Tile>();

     //Add the tile currently inhabited by the AI to the frontier and to the dictionary with a null value
     frontier.Add(GameController.tiles[(int) (transform.position.x - GameController.xOrigin), (int)(transform.position.y - GameController.yOrigin)].GetComponent<Tile>());
     cameFrom.Add(frontier[0].GetComponent<Tile>(), frontier[0].GetComponent<Tile>());
     //Flood Fill all the empty tiles the AI can move to
     while(frontier.Count > 0){
         //Find the last tile added to it
         Tile current = frontier[0];
         foreach (Tile t in FindNeighbors(current.transform.position)){
         //    Debug.Log (cameFrom.ContainsKey(t) + " " + t.transform.position);
             if(! cameFrom.ContainsKey(t) && !t.isFilled){
                 frontier.Add(t);
                 cameFrom.Add(t, current);
             }
         }
         frontier.RemoveAt(0);
     }
     //Construct path start at the goal
     Tile currentTile = GameController.tiles[(int) (target.x - GameController.xOrigin), (int)(target.y - GameController.yOrigin)].GetComponent<Tile>();
     Tile startTile = GameController.tiles[(int) (transform.position.x - GameController.xOrigin), (int)(transform.position.y - GameController.yOrigin)].GetComponent<Tile>();
     path.Add(currentTile);
     //And work backwards until you get to the current position
     while (currentTile != startTile){
         try{
         currentTile = cameFrom[currentTile];
         path.Add(currentTile);
         }
         catch{
             Debug.Log("Key Not Found");
             Debug.Log("Current Tile is" + currentTile.transform.position);
             currentTile = cameFrom[GameController.tiles[(int) (target.x - GameController.xOrigin), (int)(target.y - GameController.yOrigin + 1)].GetComponent<Tile>()];
             path.Add(currentTile);
         }
     }
     path.Reverse();
     path.RemoveAt(0);
     return path;

 }

Now for the strange part. When my first wave is generated all the enemies are spawned without error. However, when the next wave is spawned if an enemy is ever spawned on the same tile that an enemy was generated on previously the FindPathTo method raises the following exception

 KeyNotFoundException: The given key was not present in the dictionary.
 System.Collections.Generic.Dictionary`2[Tile,Tile].get_Item (.Tile key) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Collections.Generic/Dictionary.cs:150)
 Pathfinding.FindPathTo (Vector2 target) (at Assets/Scripts/Pathfinding.cs:47)
 Enemy.Start () (at Assets/Scripts/Enemy.cs:41)

I implemented a try-catch to print out all the values in the cameFrom dictionary whenever the exception was raised and found that the tile that the enemy was starting on was in fact not in the dictionary so I basically tried to force it in whenever the exception was raised, adding the tile to the dictionary results in even stranger behavior, sometimes it will cause everything to run perfectly well other times it will freeze the game for about 30 seconds then give me the following exception.

 ArgumentException: An element with the same key already exists in the dictionary.
 System.Collections.Generic.Dictionary`2[Tile,Tile].Add (.Tile key, .Tile value) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Collections.Generic/Dictionary.cs:404)
 Pathfinding.FindPathTo (Vector2 target) (at Assets/Scripts/Pathfinding.cs:56)
 Enemy.Start () (at Assets/Scripts/Enemy.cs:41)  

The only workaround that I found that allows everything to run smoothly is the one you see in my code above, where I simply skip down to the second tile whenever the exception is raised. I've ran through about 15 waves with this code without getting any errors.

I guess my question is 1) Why does this error only occur after the first wave? 2)Why does it only occur when an enemy starts on a tile that an enemy previously spawned on?

EDIT: Edited to reflect new strange behavior regarding the "force add" workaround