Unstructured grids have their place.
You may want to look at the Earth System Modeling Framework (ESMF). They have some code for re-gridding -- specifically for this purpose -- and they've done some nifty stuff with parallel code, too. The whole system is designed to couple models, so there may be other useful stuff there as well.
Some other notes:
"no way to do this efficiently for any significant number of points"
well, efficient is a relative thing -- once you've got the grid in a tree structure, you can search it in O(logn), which can be pretty darn fast, though not O(1), as searching a regular grid is.
Also, it sounds like while the interpolation needs to be done at every time step, if the grids aren't adapting, then the mapping from one grid to another remains constant. So you can compute that mapping (i.e. which element in each grid corresponds to which element in the other) in whatever way is convenient, store it, and then you never need to compute it agin (until the grids change).
That leaves you with the interpolation code -- where you will want to balance accuracy with performance -- simple linear interpolation across a triangle is fast, and may be good enough.
"I thought about using kd-tree for searching the nearest node of a given point, then I would use the shape functions of that element"
remember that the nearest node doesn't get you the element -- so you'll want to do a bit more to find the element you want. One option would be to use an rtree instead, which stores/searches by bounding box -- you'll get more than one element with each search, but you can then check which of those is correct directly.