You shouldn’t use $_GET['s'] directly like that, and you definitely shouldn’t use query_posts, although I understand using it for testing.
If you’re going to build your own search mechanism in this way, then you should run $_GET['s']through the urldecode() function first, to make sure it doesn’t contain weird data that you might not expect and which could muck up your search.
Realistically, just adding the post_type to the search form will make it search that post type automatically, you don’t need to do your own query_posts call. The only thing left to do is to make sure you have the post_type correct (it is “companies”, right?) and to make sure that there actually is content containing whatever you’re searching for.
Searching works fine with custom post types. There’s nothing special or specific that needs to be done to make it work.
Make sure that the post type is a public type, or doesn’t have the “exclude_from_search” flag set for it.