I wouldn't call myself a full "regex expert" (I consider some other monks the real experts :-) ), so there might be a better way to do this, but I do know the trick to use a dot and negative lookahead to say "match anything, except this thing I don't want to match", similar to "[^"]+". This works:

use warnings;
use strict;
use Test::More;

my $re = qr{ \b type = "([^"]+)"
    (?: (?!<\w+TagIwant\b) . )* <(\w+TagIwant\b)? }msx;

is_deeply [
    q{ <blah1 phase="2" type="MyType" more_keys="Values" <Unwanted/>  
+<SomeTagIwant><k1="v1"></SomeTagIwant> }
        =~$re], ['MyType','SomeTagIwant'];
is_deeply [
    q{ <blah1 phase="2" type="MyType" more_keys="Values" <Unwanted/>  
+<SomeTagIwant/> }
        =~$re], ['MyType','SomeTagIwant'];
is_deeply [
    q{ <blah1 phase="2" type="MyType" more_keys="Values" <Unwanted/>  
+<SomeTagIwant k3="v3" /> }
        =~$re], ['MyType','SomeTagIwant'];
is_deeply [
    q{ <blah1 phase="2" type="MyType" more_keys="Values" <Unwanted/>}
        =~$re], ['MyType',undef];

done_testing;
[download]

Update: Possibly interesting related reading: [OT] Thoughts on Ruby's new absent operator?. Also a few minor edits for clarity.