To be more clear about what I'm hoping to get, I'll share my experience.
I had a 2.1 cm AN on the left side. I had a translabyrinthine resection in July of 2005. My postop instructions were to walk as much as possible, then find things that made me dizzy and do them until they don't. I was not offered any formal vestibular rehab or the like. As an aside and as a disclaimer, I'll say that I am a General Surgeon. For those of you who are not familiar, this basically means I'm like the most goal oriented person you've ever met, but hopefully in a good way.
After a bit of a battle (friendly disagreement about the necessary length of stay) with my surgeons, I was discharged on POD #3 from Mayo (Minnesota). On the day of discharge I walked around the block in Rochester and it took me over an hour and wiped me out for the rest of the day. The next day I returned to the Twin Cities and started a maniacal program of walking. I had good shoes (Lowa low hikers) and wore them out over the next 6 weeks. By the end of week 2 I was literally walking at least 10 miles a day. It often took most of the day, but other than sit around and feel dizzy, I didn't have much else to do (and I'm not one to sit about and do nothing). I walked, napped, and walked some more. Sometime around the 4th week I was feeling like I'd accomplished the first task and started to look for things to be more challenging. The ultimate challenge, I found, was walking with my eyes closed. Such an amazing challenge for my poor proprioception system! (explained below). Most of the times that I tried that particular challenge I would have someone with me as a spotter. I'd recommend that for those of you that want to try it because I found myself walking off the path by 10 steps. More than once I actually turned in a circle! It took me about 4 months, but I ultimately was able to take 25 "normal" paces with my eyes closed and stay in a (relatively) straight line.
I returned to work 1/2 time in the 5th week. I returned full time in the 7th week. I had to make a lot of accommodations at work, I had to change the way that I do some things, but I never looked back.
Prior to my surgery, I had been involved in Tae Kwon Do for years. I had progressed to the level of Red belt and would have been eligible for test for my Black belt in November of 2005 had I not had the surgery. I was forbidden from resuming training by my surgeons for 6 months. I would have gone back earlier had my SO not heard their instructions! Nonetheless, in January of 2006 I resumed my TKD training. Whatever I had done before did not prepare me for the immense challenges this presented to my system. I had many days where I would literally crawl off the training floor on hands and knees hoping to not throw up from vertigo. It took me 16 months of serious work, but in July 2006 I tested for and achieved my Black belt.
I tried riding bike in 2006 as well. I have been able to ride since then without too much problem as long as I don't look over my left shoulder. Doing so usually ends up with me swerving all over the road!
In summary, then, I think that a program of reasonably vigorous physical exercise in the first few months, followed by a prolonged effort at doing very challenging things for my balance has been an amazing boon to my recovery. Honestly, most people I meet have no idea that I'm deaf in one ear, that I have any issues with balance, or that I ever had brain surgery. Those who know me well know that I still struggle. I fall over, fatigue pretty quickly, avoid walking in the dark, and other issues.
I'm anxious to hear your success stories!
For those that are interested, here is proprioception. Basically, the balance system of "normal" people is like a three legged stool, with the eyes acting as one leg of the stool and each inner ear acting as the other legs. The inner ear is very much like a gyroscope that helps you determine your position in space. After the AN surgery has removed one inner ear, you have a three legged stool with 2 legs. Not such a stable configuration any longer. Put an AN patient in a dark room and you're now on 1 leg and most of us are, more or less, all over the place.
Like everything in nature, though, you'll adapt to things that don't kill you. You didn't die of your AN surgery, so now you have to adapt. Your brain needs to figure out a way of making up for that missing leg of the 3 legged stool. The answer is proprioception. There are little nerve receptors that sense the position of the parts of your body relative to one another. Think of the Romberg test, which they probably make you do at each check up. Stand with your feet together, arms outstretched in front of you, palms up. Close your eyes. Feel your ankles start to wobble? Feel the muscles around your hips and knees start to fire? That's your body using proprioception to try and balance. Your brain is testing the tension around your joints, trying to fine tune it to bring you into balance. Does it work? Yes, it actually works surprisingly well. The problem, as best I can tell, is that it's a lot of mental work and it tires you out. So, the more you do to tune the system (walking, etc.) the more efficient it becomes.
Hope that helps.