An entity is at X, and wants to pathfind to Y. The first step is to find the closest waypoints to X and Y. How do you generally do this? I store my waypoint graph as point + adjacency list. I also have an area map, so I can lookup the area easily. It's no problem if I have 1 waypoint per area, then my waypoint list just indexes by area. But now I have multiple waypoints for each area, specifically, a waypoint for each connection between areas.

How do you store your waypoints in such a way that you can easily find the closest waypoint to a given position?

EDIT: Here's a screenshot. Black dots are the old waypoints (indexed by area), white lines are the graph I'm trying to work with now.

Your number of nodes is very low. A simple iteration through the list of nodes doing a search for the nearest one should suffice. (We do this with graphs of ~20000 nodes with no real issue performance-wise.)

If - and only if - you profile that method and discover it to be prohibitively slow, you can use a spatial subdivision structure like an octree or (ideally) a kd-tree to store the node information. A left-balanced kd-tree can be stored in a flat array with only a few "gaps" (i.e. unused indices in the array), so that's a decent option for memory conservation if you need it.

Ok, cool. I wasn't sure if brute-forcing would be just way too slow to scale (there are 222 waypoints on the map, that screenshot is just a portion), but I'll stick with it for now.

Yeah... if 222 distance measurements kill your processor, there's seriously something wrong. Go for it!

Fixed waypoints (waypoints that move around or that are added temporarily may be processed separately) could be sorted in a way that allows far ones to be clipped and ignored, without requiring complicated indexing systems or non-sequential memory access.

For example, if waypoints are sorted along a certain Cartesian coordinate (the sparsest one works better) we can start from an arbitrary place (e.g. the previously closest waypoint) and scan the array of waypoints before and after that position until the projected distance between candidate and query point along the chosen axis exceeds the distance from the current best candidate.

You just described two thirds of the implementation of a kd-tree.

If you only wish to search for waypoints in the current area, then you can try storing a list of which waypoints are in each area. How coupled you make this to the area structure is up to you. For example, you can store which waypoints are in each area in a single big array, and then index into it based on the area. For example:

// This is used to store which waypoints are in which area. Area[0]'s waypoints are first, followed by Area[1], then Area[2], etc. Stored values are indices into the waypoint list (or pointers to waypoints).
int g_area_waypoints[1000];

struct Area
{
... // your usual data here.

int waypoint_indicies_start; // where in g_area_waypoints the waypoints for this area are kept.
int waypoint_indicies_count; // how many waypoints in this area.
};

Thus rather than searching every waypoint, you just search from g_area_waypoints[waypoint_indices_start] to g_area_waypoints[waypoint_indices_start + waypoint_indices_count - 1]. Pretty easy to setup and requires minimal extra processing time to build the list. I have shamelessly stolen the idea from id's BSP format, which uses index lists everywhere. Reduces any additional processing required after the map has been loaded to zero, and allows you to pretty much load the entire section into memory and setup a couple of pointers to the start of the lists and be done.

As with anything, the reduced runtime processing time is at the expense of more memory, but with small map sizes the extra overhead should be negligible.