well, A* returns the shortest route, yes... UNLESS you weighten the waypoints
By giving them a cost and taking that in account during pathfinding, you can make dangerous routes appear longer to the pathfinder while safer routes will appear shorter. See what I mean ? Currently your pathfinder only sums up the distances between waypoints I suppose. Well just make it sum up the kills/death ratio per team for each waypoint also. Each time a player is killed, see what are the nearest waypoints and add to these waypoints' danger values.
Look at sPlOrYgOn's POD-bot for Counter-Strike: each time you frag the bots on a particular route, the next round they take others and manage to outflank you pretty well.