First of all, how did another AI destroy a starbase without declaring war? I thought any attacks would result in war...
Can you see all five ascension crystals? I think only five are ever spawned, regardless of map size or number of opponents. Are you absolutely sure they don't control any ascension starbases? If you can't actually see them (as in, you revealed them, but they're in the fog of war), there's a chance they rebuilt when you weren't looking.
About the starbase sharing U.P. law, isn't that just for allies? Is there an alliance between that race and one that currently has an ascension starbase? If so, is it possible to instigate a war between them to break the alliance, or do you get some "I can't betray my allies" line? If that's the case, you may have to destroy the ascension base yourself. Oh, and if you go to the foreign relations menu, United Planets tab, you can check all laws currently in effect.
I'm fairly new to this game myself, and I play with ascension off, so this has me stumped. Let us know what happens!