Thanks all, I can see whats going on now and I understand why it's happening but I'm still at a loss as how to avoid autovivification without breaking up the origional pattern into parts and testing them one at a time.
Roger: Because 'exists' still wont stop autovivification your solution above will still muddy the origional structure (If you Dumper($data) after searching you can see empty foo => {}'s everywhere.)
Update: For future reference I found
this article(perlarchive.com) which had an example sub to get me started on testing deep structures without triggering autovivification.