Did you have an advisor of studies while you were an undergrad? I'm sure they'll well used to writing references for students who've been away from uni for a few years. Even if a lecturer has moved, could you not find out where they've moved to and contact them there? After all, it's you they'll be writing about, so it doesn't really matter where they are - all that's important is that they taught you at some stage!