I don't know if there's any golden answer here, but I do have a couple of suggestions.
First, I'd dispense with any inquiries into things like optimizing Math.PI/180, and so on. The generally high framerate should make it clear that simple calculations are not slowing anything down.
Second, to address the occasional spikes of display lag: These look to me very much like the garbage collector is running very frequently. On a very brief look through your code I didn't see any obvious causes of frequent GCs, but I do have two suggestions. First, if you have access to the Flash IDE, I'd try recreating your project without using the Flex framework. A Flash project doesn't include any code except what you put in, but Flex employs a lot of its own arcanery, which may not always be obvious, and some interaction between your code and the framework might be causing GCs.
If that doesn't help, the other thing to try would be to make a greatly simplified version of your code (in Flash if possible), which would hopefully be simple enough not to trigger the same spikes. I mean, for example, a single class attached to the graphic, which merely has one listener for key events and a second listener for frame (or timer) events, within which no variables are created. If a minimal version doesn't display these spikes, then it ought to be possible to triangulate between that and your full client, to figure out what's causing the spikes.
Finally, regarding the general smoothness, my only comment would be that Flash's screen updates are inherently slightly uneven, and realistically you only have two approaches available. Either you move your actors according to frame updates, which makes their movement slightly uneven as framerates vary, or you move them according to elapsed time, which makes their overall movement smooth (in pixels per second) but their display slightly uneven (in pixels moved per frame). The difference is magnified at higher FPS.
Also, it's important to remember that after Flash has made its updates, how they appear on your screen is heavily influenced by your video card. Especially you'll find that shearing and vsync issues can be highly noticeable in one environment and absent in another. There's no real way the developer can address this, except to generally avoid very high-FPS animations and keep the overall processor burden as low as possible.
edit: For more on what I mean about frame update timing being "inherently uneven", please see this blog post. The delay between screen updates varying between 12-16ms is not something you can do anything about; it's a result of the fact that the OS and the browser influence the way Flash's timing works. (It's also something you'll see even in an empty movie, which is why the many comments in this thread about optimizing math and so on are not going to help you.) You can't avoid this kind of variation, but as I said above, you can tailor you visual effects to evoke the effect you want. Either way, I think the spikes are much more worth worrying about. The variation you're looking at is subtle, and will be hard to notice in a game with lots of stuff going on, but the spikes are egregious.
edit 2
You ask: "Do you really think that those smooth games use the same movement algorithm as I do?"
The answer is, I think they're doing something much simpler. They're almost certainly doing one of the following:
function onEnterFrame() { // move at a constant speed per frame
ship.angle += dtheta;
ship.x += speed * Math.cos( ship.angle );
ship.y += speed * Math.sin( ship.angle );
}
function onEnterFrame2() { // move at a constant speed per second
var dt:Number = getTimeSinceLastFrame();
ship.angle += anglePerSecond * dt/1000;
var dist:Number = speedPerSecond * dt/1000;
ship.x += dist * Math.cos( ship.angle );
ship.y += dist * Math.sin( ship.angle );
}
In other words, either move a constant distance per frame, or a constant distance per second. Those are the two simplest ways you can approach this, and are the two options that are going to result in the smoothest appearance in Flash. They'll look identical at a constant framerate, and the latter method will look smoother at slightly varying framerates for reasons similar to the "temporal aliasing" mentioned in the article you linked. But the choice between these methods really comes down to, if a CPU spike occurs, after it's over do you want the ship to have kept moving or not? Which is really a game design question. One thing I've done in the past is to use the second method, while clamping dt to at most 2 or 3 times the duration of an ideal frame (1/fps).
As you've probably noticed, the two methods I just recommended are exactly what the "Fix your timestep!" article says not to do. This is because that article is about numerically integrated physics engines, and that's not what you're doing. If you start implementing springs and gravity, then yes, whenever the timesteps get large it will introduce a lot of error, because for that kind of simulation, to oversimplify things, the error depends on the size of the timestep. In what you're doing, it doesn't, so occasional large timesteps don't affect the correctness of the simulation.
Reply to update 6
First, I didn't tell you your problem was performance, I specifically said the opposite. I suggested a minimal reproduction because I believed your problem was either somewhere else in your project, or unavoidable, and I still do. Second, I now feel pretty comfortable saying that you're doing things the same as any other Flash game, and whatever problems you see cannot be solved other than in perception. In the new links you posted, the animation looks perfectly smooth if I view it in the standalone SWF player, and has subtle flickering at the front and back edges in browsers (moreso in Firefox than in IE). Technically, I don't think it can improve (especially when it's basically perfect in the standalone player, implying that any choppiness in browsers is influenced by the container.)
Of course, the perceived performance can still improve. If the ship didn't contrast so sharply with the background, for example, the flicker would be much less noticeable. Also, simply making the ship move more slowly would make the movement appear much smoother, and could be combined with a moving background to give an illusion of greater speed (as one of your examples did).
As a sanity check, here's a similar minimal version I made in the IDE.
http://www.fenomas.com/random/ship/
The performance is comparable to yours on my machine, and as I said, I really don't see any problem. (Except the occasional spike, which I now notice only occurs for me in Firefox.) Again, especially the fact that both versions appear basically perfect to me in the standalone player further convinces me that there's no golden algorithm here. I know that's not the answer you want, but it's the one I got.
