Little tips, you should separate entities into separate lists based on its type (alive, movable, etc) so it can reduce the looping time, since you need to perform this a lot.
Thanks for the tip. I've already done this in the way that path finding for each entity is done.
Are you setting the actual "moving target" as target or some sort of simple prediction? (Like p.e. x tiles into the direction the target is walking, where x is the distance between the chasing entity and the target now)
Depending on how much cpu you can afford to waste and how you want your entities to "react", you can get some neat looking "behaviour" by just messing around a little with the way the fake/prediction-target gets chosen or even comparing multiple fake targets (doing pathfinding from target to its potential goals first + choosing something on that path as target instead of the actual target itself can have neat results too).
If something like that makes sense can depend a lot on exactly how your game / levels look though, so maybe you should post a screen-shot or something in the hope that someone who's more experienced that me can give you more specific advice.

Currently I'm just setting the "moving target" to the target's actual location. I'll play around with estimating where the target would be after x number of moves though, thanks for the suggestion

I'm not sure how helpful a screenshot would be, as I don't have any of the final level designs done. I'm currently in the process of implementing features.
What I did for Guardian II is this:
1. Check if target is alive. If not, cancel.
2. If target is targetable with simple AI, switch to simple AI. Otherwise, continue:
3. Check if path to target has been found. If not, find a path.
4. Check if you are on the path. If not, try to get on path. If still not, find new path.
5. Check if target is within a certain distance of the path's end point. If not, find a new path.
6. If at end point and target not targetable with simple AI, find new path to target.
By 'simple AI' I mean, if target is left, go left. If target is right, go right etc.
I hadn't thought about separating it out into a simpler AI and a more complex one. However, I'm worried that determining if simple AI will work and then having to resort to complex AI would just worsen the performance problems. Perhaps I'm misunderstanding your explanation though.