Aeonaxx typically spawns twice a week, the absolute minimum is 6 hours. TLPD's got a minimum of 45 minutes, but that is only when other rares are being killed in Northrend. The way TLPD's spawn works is that every time Vyragosa is about to spawn, there's a small chance TLPD will take its place. So TLPD shares spawn points and timers with Vyragosa. Remember that ALL rares in Northrend are linked and the more rares you kill in Northrend, the greater chance Vyragosa (or possibly TLPD) will spawn. In Deepholme however... the rares are not linked in any way. If you ever here Aeonaxx is linked to the rare spawn Bloodseeker, he's not. And to answer the NPC scan going off and Aeonaxx is nowhere to be seen... Somebody else most likely mounted him and he just flew out of sight. =/
I spent 9 hours on and off until I found TLPD, spent about a month just checking Deepholme, and 3 days hardcore camping until I got him.
Hope some of this helps.
linked to Blood Seeker though the rest of your post is correct. Blood Seeker is Vyragosa to Aeonaxx's TLPD. Unfortunately, the bat has a much, much smaller visual range and is bugged, as of 4.3, in that he will despawn a few seconds after spawning so the odds of missing a bat spawn are quite high.
If you're serious about camping either of these, read up:
tlpdresource.com and aeonaxxresource.com
TLPD Resource video: http://www.youtube.com/watch?v=yNkVBFwsTVo
The only variation I've found is that it's relatively easy to determine typified TLPD/Vyra spawns for your OWN server based on traffic. For example, on US-LS, if no one was out pushing NR rares, a Vyra/TLPD spawn showed up every 11-13 hours (results based on two weeks of camping). The one time that I watched two people actively pursuing Frostbitten, a Vyra showed up six hours after the last. As a result, I gave myself a ten-hour break in between spawns. It was a risk as I don't know who might be looking for rares but I was confident in my server to continue its tendencies during my camp. For my TLPD camp, I parked my main shaman on the FL spawn point (NOT in the path) and an alt shaman on the Brunn spawn-- every waterfall and ULd spawn made it to me as the only other campers I saw decided to sit at the multi-path (which can't see spawns). During my camp, I tagged every.single.Vyra.successfully=) It took around 16 Vyras before a TLPD showed up.
After landing TLPD, I moved on to Aeonaxx. It's been about a week. I sit on a spawn spot and I can see two other spawn points from this spot. I have not added a second camper to the opposite spots yet (accepting the risk that I might miss those spawns) but as I logged in last night (stopped to visit the grocery store) to see that not only had Aeonaxx spawned on my camp, but I missed the chance to tag him by the most literal definition of 'a second,' I'm tempted to add the second account to the mix again. This is a much quieter camp (no random PvP) as the spawn windows are larger and almost impossible to keep track of as an individual. I haven't seen any other serious campers (just a couple repeat names who log on for an hour or so at a time) so sharing notes hasn't been much of an option. Other than that one disappointing log, I've seen a Xariona (not linked) which I killed on my DK as a way to break the monotony.
Anyway, read up on the linked pages. There are a lot of outdated (and false) theories still being pushed. Yes. Blood Seeker and Aeonaxx share spawn spots/timers unfortunately. Unlike TLPD and Vyra however, there's nothing you can do to speed up the frequency of their spawns.
A final note: as suggested by Ponderance, get both NPCScan and Silver Dragon. I wouldn't bother with Overlay. I can't speak for Aeonaxx-- both went off when I logged in sitting on his nuts but there were multiple times that despite my cache being cleared, SD alerted me to a Vyra while NPCScan simply cached the spawn without sounding an alert.