How about a "new player certificate" ?
All depends on what you are able to check and how much effort PA team is willing to put into it though, but just some random ideas.
upon signup a player can certify to be new to PA (and at the same time register his nick)
PA team then can check ip's and mac addresses from where connection is made to verify if the new player is indeed new.
deterrant from cheating -> punishment at the earliest 1 week into the game with reset of account, auto exile, change race into something random, anarchy for 500 ticks and the abilities to self exile, reset and create new account turned off. Also any purchased credits are voided for that email account.
(in short, pls do not abuse newbie status, if you do and get busted, you'll be butthurt worse than just getting closed
)
Alliances get 5 extra spots for certified new players, those players do not fill regular spots even if they join the ally first untill all 5 certified new player spots are filled.
a certified new player spot remains filled once filled. it's up to the alliance to keep their players active, interested and honest.
Defending a certified new player (against player x) provides the same amount of xp as an attack (on player x) would provide, with a minimum of 50 xp
Helping a certified new player attack (by flying alongside) provides the same amount of xp as what the new player gets.
(this should be most beneficial for late starting newbies)
If a certified new player finishes the round (in a same ally & gal for 500 ticks or more) and returns next round and remains active for at least 30 days during that next round, both the alliance leader and the gc get 1 credit.
Of course, all of this depends on how well it can be verified if someone is actually new. This is also why I am in favor of (in my opinion) harsh punishments to any attempt to abuse.