Wordpress - Strange permalink issue: can't rename /company-2/ to /company/

Check the slugs of the other pages - chances are /company/ is being used for one of those. You could also go to /company/ on your site and see if anything pulls up.

As mentioned in a comment, make sure to check the trash as well. You may have deleted a page with that name, but if it is still in the trash you can not reuse the name.

You're close. The permalink cannot be changed because at some point another page titled 'company' was drafted (not necessarily published). Unfortunately, there isn't much that I know of that you can do from WordPress to change this besides naming the page something else. However, you could go into the database if you have access and look in the 'wp_posts' table. Keep searching under the 'post-title' column until you find one that is simply 'company' and delete it. This should, in theory, solve your problem.

I had the same problem and did everything that is normally suggested (empty trash etc)..I found the problem was that I had an image in the gallery with the same name as the page. Deleted the image, uploaded it with a new name and the problem disappeared.