Is there a way to query the "All Contacts" table in Mobile Connect?
It seems the Filter does not have an filter parameter for not begins or any other way to include such search criteria.
Have your starting population as 'All Contacts' when creating the Mobile Connect filter.
If you want to filter only contacts that are in your MobileConnect environment, then select MobileConnect Data Attribute Library - you can then filter on Contact ID
If you want to filter contact keys across the Marketing Cloud Contact Model, then you can use the System Data Attribute Library
If you wanted to just filter 'everyone' then you could use
Contact Key is not null
This would return you everyone who has a Contact Key or similarly the Contact ID - depending on what you want to filter/find
In answer to you specific question - 'Not Begins with' is not a filter operator that is available in mobile connect - you should raise it as a feature request/idea with Salesforce.
Two ways I can think of that could active a similar result (not ideal though)
1) Create an additional attribute in MobileConnect and using SQL, populate it with the 'begins with' values e.g. if you want the first 3 characters of the Contact Key then you use SQL to populate your custom attribute with the first 3 characters. You can then use the 'not equals ' filter operator.
2) Create a Filter using the 'Begins' operator and save your result as a Suppression List - then send to your full audience list and suppress this suppression list.
Neither solution is ideal - #1 would probably be the safer/easier route if you understand SQL and adding custom attributes to the MobileConnect contact model