I am using Custom Post Template that we associated with Magic Fields to produce custom publish type named Company.
I additionally produced custom taxonomy named City. City is hierarchical (like groups), and each Company has one city selected.

For instance:
I've got a company with publish title Microsoft and City taxonomy Redmond selected. I would like my permalinks to appear such as this:

Much like if you have a publish category and wordpress prepends first category selected for your permalink.
Will it be achieved?

I've not attempted the wordpress plugin combination you pointed out but "normally", the permalink you would like are only able to be accomplished with category entries OR pages. What you would like is one thing like: http://blogurl.com/categoryname/blogpostname Which does not take place in wordpress.

Your choices are: http://blogurl.com/parentpage/childpage or http://blogurl.com/parentcategory/childcategory

I have found fix for your problem. This is actually the code:

add_filter('post_link', 'mba_courses_permalink', 10, 3);
add_filter('post_type_link', 'mba_courses_permalink', 10, 3);

function mba_courses_permalink($permalink, $post_id, $leavename) {
    if (strpos($permalink, '%mba_courses%') === FALSE) return $permalink;

    // Get post
    $post = get_post($post_id);
    if (!$post) return $permalink;

    // Get taxonomy terms
    $terms = wp_get_object_terms($post->ID, 'mba_courses'); 
    if (!is_wp_error($terms) && !empty($terms) && is_object($terms[0])) $taxonomy_slug = $terms[0]->slug;
    else $taxonomy_slug = 'mba_courses';

return str_replace('%mba_courses%', $taxonomy_slug, $permalink);