Is it possible to make a custom creature that can 'actually' fly. I know that its possible to create the illusion of flight by adding additional height to Bip01 NonAccum (or even any other bone for that matter ... like Bip01Spine for the Oblivion Imp) ... but the trick becomes all to obvious when the creature can't fly upto you from the bottom of a mountain for example.

Well, the answer is both yes and no. You can create the illusion of flight by scripting a collision box to move with your creature while the 'flight' animation is playing (check out http://tesnexus.com/downloads/file.php?id=10819). However, since creatures and NPCs use pathgrid nodes to determine their movements, you would never see one 'fly up' to you. A good example is the Imp. If you're on the top level of a fort and the Imp is on the ground level when it decides to come after you, it will follow a path along the stairs in order to get to you. So would any other 'flying' creature not being directly controlled by the Player. It's not a scripting or animation issue, just a limitation of the game engine.