This is a bug that may be related to internal bug number W-1065879. This bug specifically dealt with inputText references that would fail to work on maps, but apparently other elements fail to work correctly with maps as well. (See http://boards.developerforce.com/t5/forums/forumtopicprintpage/board-id/Visualforce/message-id/41334/print-single-message/false/page/1 for an example).

To work around this bug, you have to create a wrapper class as a list that is driven from the maps contents (independently discovered by myself, but I'm sure others have, too).

Here's your code, modified to work around the bug.

public with sharing class testtemp {
    // Public variables.
    public list<InnerClass> lstProcedures {get; set;}
    public string key { get; set; }
    
    // Contains map items for displayed list.
    map <string, innerclass> items;
        
    // Class Constructor, unchanged.
    public class InnerClass {
        public integer counter  {get; set;}
        public InnerClass() {
            counter = 0;
        } 
        
        public void edit(){
            counter++;
        }
    }
    
    // Default constructor.
    public testtemp() {
        key = 'mapkey';
        lstProcedures = new list<InnerClass>();
        lstProcedures.add(new InnerClass());
        items = new map<string, innerclass>();        
        items.put('mapkey', new InnerClass());
    }
    
    // Generate a map-driven list.
    public wrapper[] getmapprocedures() {
        wrapper[] w = new wrapper[0];
        for(string key:items.keyset()) {
            w.add(new wrapper(this,key));
        }
        return w;
    }
    
    public class wrapper {
        testtemp controller;
        string key;
        
        // Constructor for wrapper
        public wrapper(testtemp controller, string key) {
            this.controller = controller;
            this.key = key;
        }
        // Proxy retrieve InnerClass
        public Innerclass getItem() {
            return controller.items.get(key);
        }
        // Proxy call InnerClass
        public void edit() {
            controller.items.get(key).edit();
        }
    }
}

<apex:page controller="testtemp">
    <apex:form >
        <apex:repeat value="{!lstProcedures}" var="procedure">
            {!procedure.counter} <apex:commandLink action="{!procedure.Edit}" value="Edit"/>
        </apex:repeat>
        <apex:repeat value="{!mapProcedures}" var="var">
            {!var.item.counter} <apex:commandLink action="{!var.item.Edit}" value="Edit"/>
        </apex:repeat>
    </apex:form>
    
</apex:page>

You still get the benefits of using a map from a controller point of view by exposing the data to Visualforce as a list.