I can think of several solutions:
1. Ignore Newbies when sorting on "Last post" date. This way, Newbies can't bump threads anymore.
2. Nuke all Newbies who have deleted more than x (say x=2, make it x=5 if they have more than 14 posts) of their own posts.
3. Take away the possibilities for Newbies to delete their posts.
4. Require a captcha for Newbies for either posting and/or deleting a post.
5. Create "deletelog.php", similar to
https://bitcointalk.org/modlog.php but for all posts deleted by Newbies (this would be a first step to hunt them down, not a solution to the problem).
The deletelog.php does look like an interesting idea. While those accounts which have been detected are newbies, it won't take long for the person behind these accounts to farm them up to junior member rank. If at all any restrictions are imposed, they should cover junior members as well.